Haskell递归数据类型与状态

Question

我想解决如何计算以下内容。

给定一个根值，找到以该值的最后一个字符开头的所有值。显然，如果元素已经在路径中使用，则不会重复元素。找到最大深度（最长的航线）

因此，例如与种子"sip"和文字：

t1 = ["sour","piss","rune","profit","today","rat"] 

，我们将看到最大的路径是5

siP 1 --- 
    |  | 
    |  | 
    pisS 2 profiT 2 
    |  | 
    |  | 
    |  todaY 3 
    | 
    souR 3 --- 
    |  | 
    |  | 
    runE 4 raT 4 
      | 
      | 
      todaY 5 

我想我在正确的轨道上与以下 - 但我不能解决如何实际递归调用它。

type Depth = Int 
type History = Set.Set String 
type AllVals = Set.Set String 
type NodeVal = Char 

data Tree a h d = Empty | Node a h d [Tree a h d] deriving (Show, Read, Eq, Ord) 

singleton :: String -> History -> Depth -> Tree NodeVal History Depth 
singleton x parentSet depth = Node (last x) (Set.insert x parentSet) (depth + 1) [Empty] 

makePaths :: AllVals -> Tree NodeVal History Depth -> [Tree NodeVal History Depth] 
makePaths valSet (Node v histSet depth trees) = newPaths 
    where paths = Set.toList $ findPaths valSet v histSet 
      newPaths = fmap (\x -> singleton x histSet depth) paths 

findPaths :: AllVals -> NodeVal -> History -> History 
findPaths valSet v histSet = Set.difference possible histSet 
    where possible = Set.filter (\x -> head x == v) valSet 

所以......

setOfAll = Set.fromList xs 
tree = singleton "sip" (Set.empty) 0 

Node 'p' (fromList ["sip"]) 1 [Empty] 


makePaths setOfAll tree 

给出：

[Node 's' (fromList ["piss","sip"]) 2 [Empty],Node 't' (fromList ["profit","sip"]) 2 [Empty]] 

但我现在不知道如何继续。

Answer 1

您需要实际递归地继续。在您的代码中，如现在所示，makePaths调用findPaths，但findPaths和makePaths都不会以递归方式调用makePaths或findPaths。看到算法的机制有点难，原因有两个：首先，你用很多临时状态注释树，其次，你不必要地处理Set。

让我们剥去一些东西。

---

让我们从树开始。最终，我们只需要一个具有节点值的n -ary树。

data Tree a = Empty | Node a [Tree a] deriving (Show, Read, Eq, Ord) 

需要明确的是，这Tree相当于你Tree

type OldTree a h d = Tree (a, h, d) 

这就是说，因为最终的目标树是一个唯一的节点处饰有String小号我们要瞄准对于这样的函数：

makeTree :: String -> [String] -> Tree String 

这里，第一个字符串是种子值，字符串列表是可能的连续剩余的字符串，树是我们完全构建的字符串树。该功能也可以直接写入。它进行递归基于断给定一个种子，我们马上就知道我们的树的根的事实：

makeTree seed vals = Node seed children where 
    children = ... 

孩子们通过建立自己的子树递归地进行。这是迄今为止我们运行的算法的精确副本，除了我们使用vals中的字符串作为新种子。要做到这一点，我们需要一个将列表分割成“选定值”列表的算法。喜欢的东西

selectEach :: [a] -> [(a, [a])] 

，从而为每个值(c, extras)这样elem (c, extras) (selectEach lst)列表c:extras拥有所有的lst如果可能以不同的顺序相同的价值观。我会有点不同写这个功能，但是，由于

selectEach :: [a] -> [([a], a, [a])] 

其中，结果可分为三个部分，例如，如果(before, here, after)是一个值，然后elem (before, here, after) (selectEach lst)lst == reverse before ++ [here] ++ after。这将变成更容易

selectEach []  = [] 
selectEach (a:as) = go ([], a, as) where 
    go (before, here, []) = [(before, here, [])] 
    go (before, here, after@(a:as)) = (before, here, after) : go (here:before, a, as) 

> selectEach "foo" 
[("",'f',"oo"),("f",'o',"o"),("of",'o',"")] 

这种辅助功能，我们可以很容易地生成我们的树的孩子一点点，但是我们最终将建立太多。

makeTree seed vals = Node seed children where 
    children = map (\(before, here, after) -> makeTree here (before ++ after)) 
       (selectEach vals) 

事实上太多了。如果我们运行

makeTree "sip" ["sour","piss","rune","profit","today","rat"] 

我们生产规模1957年，而不是大小8的不错得心应手树，我们想的树。这是因为我们迄今为止已经消除了约束条件，即种子中的最后一个字母必须是所选值继续的第一个字母。我们将通过滤除坏树来解决这个问题。

goodTree :: String -> Tree String -> Bool 

特别是，如果它遵循这个约束条件，我们会调用树“好”。给定种子值，如果树的根节点有一个值，其第一个字母与种子的最后一个字母相同，那么它是好的。

goodTree [] _    = False 
goodTree seed Empty   = False 
goodTree seed (Node "" _) = False 
goodTree seed (Node (h:_) _) = last seed == h 

，我们将只过滤在此基础上绕圈

makeTree seed vals = Node seed children where 
    children = 
    filter goodTree 
    $ map (\(before, here, after) -> makeTree here (before ++ after)) 
    $ selectEach 
    $ vals 

，现在我们所做的孩子！

> makeTree "sip" ["sour","piss","rune","profit","today","rat"] 
Node "sip" 
    [ Node "piss" [ Node "sour" [ Node "rune" [] 
           , Node "rat" [ Node "today" [] ] 
           ] 
       ] 
    , Node "profit" [ Node "today" [] ] 
    ] 

完整的代码是：

selectEach :: [a] -> [([a], a, [a])] 
selectEach []  = [] 
selectEach (a:as) = go ([], a, as) where 
    go (before, here, []) = [(before, here, [])] 
    go (before, here, after@(a:as)) = (before, here, after) : go (here:before, a, as) 

data Tree a = Empty | Node a [Tree a] deriving Show 

goodTree :: Eq a => [a] -> Tree [a] -> Bool 
goodTree [] _    = False 
goodTree seed Empty   = False 
goodTree seed (Node [] _) = False 
goodTree seed (Node (h:_) _) = last seed == h 

makeTree :: Eq a => [a] -> [[a]] -> Tree [a] 
makeTree seed vals = Node seed children where 
    children = 
    filter (goodTree seed) 
    $ map (\(before, here, after) -> makeTree here (before ++ after)) 
    $ selectEach 
    $ vals 

而且这将会是值得如何selectEach使用一种名为名单的拉链和makeTree如何在Reader单子操作读了。这两个都是巩固我在这里使用的方法的中间主题。

Answer 2

另外，这是我原本想要采取的方法。它使用列表作为一个集合，然后将xs的列表映射到每个x设置种子节点。然后计算最大值。

data Tree a = Node a [Tree a] deriving (Show, Eq, Read, Ord) 

follows seed hist count vals = foll where 
    foll = map (\x -> (x, Set.insert x hist, count+1)) next 
    next = Set.toList $ Set.filter (\x -> (head x) == (last seed)) 
          $ Set.difference vals hist 

mTree (seed,hist,count) vals = Node (seed,hist,count) children where 
    children = map (\x -> mTree x vals) (follows seed hist count vals) 

makeTree seed vals = mTree (seed, Set.singleton seed, 1) vals 

maxT (Node (_,_,c) []) = c 
maxT (Node (_,_,c) xs) = maximum (c : (map maxT xs)) 

maxTree xs = maximum $ map maxT trees where 
    trees = map (\x -> makeTree x vals) xs 
    vals = Set.fromList xs 

导致：

*Main> maxTree ["sip","sour","piss","rune","profit","today","rat"] 
5