Haskell List complexity

Question

sorry if this question has already been asked, I didn't find it. And sorry for my poor english.

I'm learning Haskell and try to use lists. I wrote a function which transforms a list following a specific pattern, I can't check if it works now, but i think so.

This function is not a tail call function, so I think it will be horrible to compute this function with a big list:

transform :: [Int] -> [Int]
transform list = case list of
  (1:0:1:[])  -> [1,1,1,1]
  (1:1:[])    -> [1,0,1]
  [1]         -> [1,1]
  (1:0:1:0:s) -> 1:1:1:1: (transform s)
  (1:1:0:s)   -> 1:0:1: (transform s)
  (1:0:s)     -> 1:1: (transform s)
  (0:s)       -> 0: (transform s)

So I thought about another function, which would be "better":

transform = reverse . aux []
  where
    aux buff (1:0:[1])   = (1:1:1:1:buff)
    aux buff (1:[1])     = (1:0:1:buff)
    aux buff [1]         = (1:1:buff)
    aux buff (1:0:1:0:s) = aux (1:1:1:1:buff) s
    aux buff (1:1:0:s)   = aux (1:0:1:buff) s
    aux buff (1:0:s)     = aux (1:1:buff) s
    aux buff (0:s)       = aux (0:buff) s

The problem is that I don't know how it compiles and if I'm wrong with the second function. Can you explain me how lists work ? Is it better to use (++) or reverse the list at the end ?

Thank you in advance for your answers

see also http://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons ; http://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization. — Will Ness, Feb 27 '14 at 20:22

András Kovács · Accepted Answer · 2014-02-27T17:32:25.033

The first function is perfectly fine and in my opinion preferable to the second one.

The reason is laziness. If you have a transform someList expression in your code, the resulting list will not be evaluated unless you demand it. In particular the list will be evaluated only as far as it is needed; print $ take 10 $ transform xs will do less work than print $ take 20 $ transform xs.

In a strict language transform would indeed encumber the stack, since it would have to evaluate the whole list (in a non-tail recursive way) before returning anything of use. In Haskell transform (0:xs) evaluates to 0 : transform xs, a usable partial result. We can inspect the head of this result without touching the tail. There is no danger of stack overflow either: at any time there is at most a single unevaluated thunk (like transform xs in the previous example) in the tail of the list. If you demand more elements, the thunk will be just pushed further back, and the stack frame of the previous thunk can be garbage collected.

If we always fully evaluate the list then the performance of the two functions should be similar, or even then the lazy version could be somewhat faster because of the lack of reversing or the extra ++-s. So, by switching to the second function we lose laziness and gain no extra performance.

Thanks a lot for your answer, I understand what I was doing now, so I have to count on laziness more often. I'm too used to stricts languages. — Lilymonade, Feb 27 '14 at 18:02

score 3 · Answer 2 · answered Feb 27 '14 at 17:44

Your first version looks much better to me¹. It's fine that it's not tail-recursive: you don't want it to be tail-recursive, you want it to be lazy. The second version can't produce even a single element without processing the entire input list, because in order to reverse the result of aux, the entirety of aux must be known. However,

take 10 . transform $ cycle [1,0,0,1,1,1]

would work fine with your first definition of transform, because you only consume as much of the list as you need in order to make a decision.

¹ But note that (1:0:1:[]) is just [1,0,1].

Thank you, I thought, it would not work to match [1,0,1] with the pattern matching ... but it'sjust a value, so of course it would work. — Lilymonade, Feb 27 '14 at 18:05

Haskell List complexity

2 Answers2