[Haskell-cafe] Q about last&init

[Brandon Allbery]

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

> > 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
useful.

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>