[Haskell-cafe] Q about last&init

Brandon Allbery allbery.b at gmail.com
Fri Jul 18 01:09:42 UTC 2014

On Thu, Jul 17, 2014 at 8:54 PM, Richard A. O'Keefe <ok at cs.otago.ac.nz>

> > But the original haskell functions last and init are O(n).
> Haskell lists are singly linked lists.  Even by going to
> assembly code, you could not make these operations O(1)
> without *using a different data structure*.

At this point, you may be wondering why Haskell uses singly linked lists so
much, when one might think an array/vector type might be more generally

The thing about functional languages, and in particular pure functional
languages such as Haskell, is that you don't generally have things like
looping constructs; instead, you represent your data in a form which
implies such a construct. In particular, when you might use a for/foreach
loop in other languages, in a functional language you use a singly linked
list and a map or fold over the list. (Some object-oriented languages do
this as well; consider the "each" method in Smalltalk or Ruby.)

In a pure functional language like Haskell, this can lead to optimizations
you would not get from an explicit foreach loop: since values are immutable
and can be generated lazily, a compiler can more easily recognize that it
doesn't need to generate or maintain a list at all but just consume values
as they are generated. Languages that use foreach loops often can only do
this optimization in specific cases: for example, in Perl a foreach loop on
a constant numeric range is optimized this way, but not others; in Ruby,
it's much harder to do this at all because the "each" method needs to be
resolved to a list object; and commercial Smalltalk implementations
generally have quite a lot of behind the scenes intelligence to try to
recognize and optimize these kinds of cases without falling into the same
trap as e.g. Ruby.

brandon s allbery kf8nh                               sine nomine associates
allbery.b at gmail.com                                  ballbery at sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140717/d161b6d9/attachment.html>

More information about the Haskell-Cafe mailing list