CODEWITHSUNDEEP
haskell
jhegedus
jhegedus

Reputation: 20653

Reversing a list, evaluation order

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.

Upvotes: 0

Views: 154

Answers (1)

Boyd Stephen Smith Jr.
Boyd Stephen Smith Jr.

Reputation: 3202

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.

Upvotes: 3

Related Questions