Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Haskell laziness and data structures. (Norbert Melzer)
2. Re: Haskell laziness and data structures. (Imants Cekusins)
----------------------------------------------------------------------
Message: 1
Date: Thu, 07 Jul 2016 11:40:10 +0200
From: Norbert Melzer <timmel...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Haskell laziness and data structures.
Message-ID: <87oa69dbwl....@gmail.com>
Content-Type: text/plain
OxFord writes:
> Hello,
>
> Why is there no default O(1) random access list data structure in haskell
> (for example clojure has [] vector). I would expect that this kind of data
> structure is used very often, so you shouldn't need to import one yourself.
Whenever I try to reach for something with O(1) random access, then I
have used imperative languages for too long ;) In most cases I am able
to rewrite my algorithms to work by iterating instead of random access.
And if I do not come up with such an algorithm, I then do realize most
of the time, that I do want to have a Map or Set with a certain
Key-Type, which is very unlikely to be Num.
> Is it safe to assume that ' reverse [1, 2, 3, 4, 5] ' is O(1) ?
It is not. Reversing in constant time is impossible without dooing nasty
hacks, and make it necessary to not only save distinct elements, but its
reading direction in addition.
Also to make this actually happen you need something in the spirit of
a C Array or a doubly linked list.
Also you will get in trouble as soon as you want to change an element in
the reversed collection, but not in the original one.
As soon as you want distinct containers you need to copy, and copying is
O(n) at least.
> Is it safe to assume that main =
> x = [1, 2, 3, 4, 5]
> x = reverse reverse x
> won't use more space than for the initial [1, 2, 3, 4, 5] list? (No copy of
> x)
According to my observations it is not safe to assume anything about
memory in GC'd languages.
> Why is array indexeded by ! and list by !!. Shouldn't they be both
> instances of something like Indexable?
Because indexed access is always something you should think about, and
for lists you should think about it even twice. Thats just a guess though.
------------------------------
Message: 2
Date: Thu, 7 Jul 2016 11:51:32 +0200
From: Imants Cekusins <ima...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Haskell laziness and data structures.
Message-ID:
<cap1qinzxvsikd7u6jvmhtxjt629ancncd7chcgd8jexkocz...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
> indexed access is always something you should think about,
yep, leave aside plenty of time for debugging when you use !! or "head"
with list or ! with map
package "safe" helps to safely access lists:
https://hackage.haskell.org/package/safe
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160707/fb5c3673/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 97, Issue 6
****************************************
