Haskell数据结构查找方法

lfapxunr  于 2023-05-07  发布在  其他
关注(0)|答案(2)|浏览(168)

当我在构建我的数据结构时,我发现了一个问题,我很难解决它。我的数据结构“Structure”是String和一个子结构列表。
问题出在下面的“lookFor”方法中,该方法应该在(Structurebxs)中查找名为“a”的子结构并返回它。如果不在“B”的列表(xs)中,它应该继续查找每个xs元素的列表,依此类推。如果没有找到,它应该什么都不做。
我的想法是递归,为此,我想到了“map lookFor xs”,以防它没有找到名为“a”的结构。
Ghci说“Couldn't match expected type Structure with actual type [Structure]”我理解,因为毕竟map返回的是一个元素列表而不是一个元素。

data Structure = Structure String [Structure]

name :: Structure -> String
name (Structure a xs) = a

subStrcts :: Structure -> [String]
subStrcts (Structure a []) = []
subStrcts (Structure a xs) = [name x | x <- xs]

lookFor :: String -> Structure -> Structure
lookFor a (Structure b xs) 
    | elem (elemIndex a (subStrcts (Structure b xs))) [0..] = xs !! (fromJust (elemIndex a (subStrcts (Structure b xs))))
    | otherwise = map (lookFor a) xs

有什么想法吗?谢谢

4bbkushb

4bbkushb1#

一种可能的解决方案是:

import Control.Applicative
import Data.Foldable

data Structure = Structure String [Structure]
               deriving Show

lookFor :: String -> Structure -> Maybe Structure
lookFor a s@(Structure b xs)
   | a == b    = Just s
   | otherwise = asum (map (lookFor a) xs)

上面,map (lookFor a) xs在子结构中搜索a。这将产生一个[Maybe Structure],我们使用asum来获取第一个Just _值,以便我们可以返回它。(如果没有找到这样的值,则asum返回Nothing。)
如果您不想从库中利用asum,那么定义它是一个很好的初学者练习。

nkoocmlb

nkoocmlb2#

作为递归结构,您需要设置一个基类。在你的例子中,当你用尽了列表中的所有结构时,就会发生这种情况。
作为@WillemVanOnsem,最好返回Maybe Structure,因为lookFor函数可能找不到Structure

import Data.List (elemIndex)
import Data.Maybe (fromJust, isJust)

data Structure = Structure String [Structure]

name :: Structure -> String
name (Structure a xs) = a

subStrcts :: Structure -> [String]
subStrcts (Structure a []) = []
subStrcts (Structure a xs) = [name x | x <- xs]

lookFor :: String -> Structure -> Maybe Structure
lookFor a (Structure b xs) 
    | null xs = Nothing
    | isJust maybeIndex = fmap (xs !!) maybeIndex
    | otherwise = lookFor a (Structure (name (head xs)) (tail xs))
    where maybeIndex = elemIndex a (subStrcts (Structure b xs))

相关问题