I'm looking for a smart way to get all paths traversing a given data structure. I figured out that I need a function like this:

allPaths :: (a -> [a]) -> a -> [[a]]

It takes a seed a and a function a -> [a] (from each "a", you can get to multiple a's). The result is a list of paths starting from the seed.

My definition is:

allPaths :: (a -> [a]) -> a -> [[a]]
allPaths f a = map (a:) (concatMap (allPaths f) (f a))

But it doesn't quite work:

ghci> let f a = if a == 1 then [2, 3] else if a == 2 then [4] else []
ghci> allPaths f 1
[]

The result should be: [[1,2,4], [1,3]], representing all the possible paths starting from 1.

CodePudding user response：

The problem is that as soon as you arrive at a [], you never prepend anything to that because there are no endpoints to walk towards.

Instead, [] should indicate that this is an endpoint.

allPaths f a = case f a of
  [] -> [[a]]
  fa -> map (a:) $ concatMap (allPaths f) fa

CodePudding user response：

As an alternative to the other answer, if you want all paths, not just all paths that arrive at a dead-end, then you need to prepend [] to the solution at each step, not just the final one.

allPaths :: (a -> [a]) -> a -> [[a]]
allPaths f a = map (a:) ([] : concatMap (allPaths f) (f a))

On your proposed f, this gives

*Main> allPaths f 1
[[1],[1,2],[1,2,4],[1,3]]

It includes the two paths leading to a dead end, as your example does, but it also includes [1] and [1,2], which are valid paths (they just aren't valid maximal paths). In particular, if your graph has cycles in it, then this approach will produce a valid infinite list of paths, whereas the other proposed answer will fail to produce any results as soon as it hits the cycle.