Haskell Recursive State Data Type

Question

I am trying to figure out how to calculate the following.

based on the root value, find all values ​​starting with the last character of this value. Obviously, no element can be repeated if it is already in use on the way. Find the maximum depth (longest route)

for example, with a seed "sip"and words:

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

we will see that the maximum path is 5.

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

I think I'm on the right track with the following - but I can't figure out how to actually call it recursively.

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

So...

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

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


makePaths setOfAll tree

gives:

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

but now I can’t decide how to proceed.

Answer 1

. , , makePaths findPaths, findPaths, makePaths makePaths findPaths . : -, , -, Set s.

.

---

. , n- , .

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

, "", . , node , , .

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, node 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