map of all successors for each element in haskell

Question

Given a sequence of elements, I want to find a list of all the direct successors for each element:

Example:

"AABAABAAC"

Should return something like (using Data.Map):

fromList [('A',"ABABA"), ('B',"AA"), ('C', "")]

I am aware of the fromListWith function but I can't seem to get the list comprehension right:

succs :: Ord a => [a] -> M.Map a [a]
succs xs = M.fromListWith (++) [(x, ???) | ??? ]

Why not is `ABAABAAC` successor of `A`? Where is `ABABA` successor for `A`? EDIT: ok, I understand but edit your question please. Write "for each repetition of" — josejuan, Nov 12 '14 at 09:53
I'm sorry for being unclear. I was thinking about **direct** successors. I think about the sequence as a sequence of states `A,B,C` and two neighboring states meaning a transition from one state to another. The sequence would be something like this: `A->A->B->A->A->B->A->A->C`. — fuji, Nov 12 '14 at 09:57

score 3 · Accepted Answer · edited May 23 '17 at 10:33

Does this help?

succs xs@(_:xss) = M.fromListWith (++) $ zip xs (map (:[]) xss ++ [[]])

I think it returns ('A',"ABABAC")..., your example has no C.

(:[]) is a point-free version of

singleton :: a -> [a]
singleton x = [x]

How did I get to this solution? I find this definition for the fibonacci numbers fascinating: [1] [2]

fibs = fibs = 0:1:zipWith (+) fibs (tail fibs)

A similar thing can pair up every element with its successor:

let x = "AABAABAAC"
zip x (tail x)
[('A','A'),('A','B'),('B','A'),('A','A'),('A','B'),('B','A'),('A','A'),('A','C')]

This type almost matches the input to

M.fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> M.Map k a

Now turn the characters into singleton lists and add an empty list to not suppress ('C',"").

It returns `('A',"CABABA")...` due to how `fromListWith` applies the combining function. The order can be reversed by `flip`ing `(++)`. It can also be done by adding an `fmap reverse .`. — Cirdec, Nov 12 '14 at 10:25

score 1 · Answer 2 · answered Nov 12 '14 at 10:02

You can split the problem into two parts. First, find the edges between two elements of a list.

edges :: [a] -> [(a, a)]
edges (x:y:zs) = (x,y):edges (y:zs)
edges _ = []

Then build a map to all the items that are the immediate successors of an item with fromListWith.

succs :: Ord a => [a] -> M.Map a [a]
succs = M.fromListWith (++) . map (\(x,y) -> (x,[y])) . edges

This doesn't give quite exactly what you desire. There's no entry for 'C' since it has no immediate successors.

succs "AABAABAAC" = fromList [('A',"CABABA"),('B',"AA")]

Instead we can make a less general-purpose version of edges that includes an item for the last item in the list.

succs :: Ord a => [a] -> M.Map a [a]
succs = M.fromListWith (++) . edges
    where
        edges (x:y:zs) = (x,[y]):edges (y:zs)
        edges (x:zs)   = (x,[] ):edges zs
        edges _ = []

map of all successors for each element in haskell

2 Answers2