How does scanl in Haskell work on list of Either's - comparison of two cases

Question

I am trying to use the scanl function in Haskell. I have narrowed down my problem which can be described in the following two cases, which can be run in the interpreter using just a normal library within Haskell that contains the scanl (Note that I am not necessarily interested in the Monadic value here, but just how to use scanl to ensure a type consistency):

Why does the following with pre-listed Right values work work:

*Defs> scanl (\x acc -> x ++ acc) [] [[(Right 1)], [(Right 2)]]  
[[],[Right 1],[Right 1,Right 2]]

when this doesn't work and causes the following error message:

*Defs> scanl (\x acc -> [x] ++ acc) [] [(Right 1), (Right 2)]

<interactive>:36:35: error:
    * Couldn't match expected type `[[a]]'
                  with actual type `Either a0 b0'
   ...

Answer 1

I think you have the value and accumulator swapped. Consider the type of scanl:

ghci> :t scanl
scanl :: (b -> a -> b) -> b -> [a] -> [b]

The accumulator value is of the type b. It comes first.

If you swap the arguments in your second example, it works:

ghci> scanl (\acc x -> acc ++ [x]) [] [(Right 1), (Right 2)]
[[],[Right 1],[Right 1,Right 2]]

You can also swap the argument of the first example, and that, too, works:

ghci> scanl (\acc x -> acc ++ x) [] [[(Right 1)], [(Right 2)]]
[[],[Right 1],[Right 1,Right 2]]

Answer 2

What you here aim to do already exists, this is inits :: [a] -> [[a]], it produces all prefixes. You use a list of lists, but that can be processed by concatenating instead of pretending.

Each time constructing a new list that appends at the right end will however require (n²) which makes sense, since the total construction indeed (n²). But it is possible that we want only to generate the last lists for example.

Therefore it might be better to work with a difference list, which allows to append one element in (1) and thus will eventually take only (n²) time if we wish to only construct one of the last items for example:

dapp :: [a] -> ([a] -> [a]) -> [a] -> [a]
dapp [] f = f
dapp (x : xs) f = dapp xs (f . (x :))

dground :: ([a] -> [a]) -> [a]
dground = ($ [])

so we can construct the function as:

ourInits :: [[a]] -> [[a]]
ourInits = map dground . scanl (flip dapp) id