0

enter image description here

I am reading page 69 of Haskell School of Expression and I am not sure that I got the evalution of rev [1:2:3:4] right.

Hudak does not explain the evalution(rewriting) order in detail in his book for reverse.

Could someone please either confirm that my guess (shown in the attached picture) is correct or if not correct then point out what I got wrong. I believe that it is correct but I am not 100% sure, this is the reason for asking.

So the question is:

when I evaluate one step of reverse then aftes the evaluation (i.e. rewriting) the result should be surrounded by parenthesis, right?

If I understand correctly, these unlucky appearance of parentheseses is the reason for the poor (read quadratic) time complexity of reverse. In this example 6 steps are spent in total on list appending in order to reverse a 4 element list.

jhegedus
  • 20,244
  • 16
  • 99
  • 167
  • 2
    It looks like just a "typo", but your definition for `rev` is wrong, you should be using `++` not `:` on the right hand side of the `(x:xs)` case. – bheklilr Jul 21 '14 at 18:49
  • 2
    It looks like you have the evaluation order correct, but for some explanations of why this is slow, check out [this](http://stackoverflow.com/questions/23874719/why-haskell-list-is-more-efficient-if-its-left-associate/23874845#23874845) question. – bheklilr Jul 21 '14 at 18:51
  • Thanks bheklir, indeed that is a typo. – jhegedus Jul 21 '14 at 22:13

1 Answers1

3

Yes, nested, left-associative calls to append (in Haskell, goes by the names (++) and (<>)) generates poor performance of singly-linked lists.

There are several solutions to this problem, since it's been known about for 30 or 40 years, at least. I believe the library version of reverse uses an accumulator to achieve linear complexity rather than quadratic, but it's still not something you want to call frequently on lists.

Boyd Stephen Smith Jr.
  • 3,182
  • 14
  • 39
  • @DanielWagner Doh! You're right, I must have read the output wrong because I typed it in to check. But the `foldl' (flip (:)) []` implementation does actually reverse the list. – bheklilr Jul 21 '14 at 19:52