Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
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. (Ford)
2. Re: Haskell laziness and data structures. (Norbert Melzer)
----------------------------------------------------------------------
Message: 1
Date: Sat, 09 Jul 2016 14:54:40 +0200
From: Ford <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Haskell laziness and data structures.
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
I am trying to implement ant colony optimization algorithm (or any other
similar simulation) . In procedural language I would keep the world map in 2D
matrix that provides O(1) collision check and O(1) ant position change.
Should I try to implement this in haskell in the same way (2d mutable matrix)?
If yes, what data structure should I use?
If not, how can I achieve the same performance as in procedural style?
(The memory usage is also important.)
Thank you for any tips.
King regards,
Ford
Odesláno z BlueMail
7. 7. 2016 11:40 AM, 11:40 AM, Norbert Melzer <[email protected]> napsal/a:
>
>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.
>_______________________________________________
>Beginners mailing list
>[email protected]
>http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160709/a6253025/attachment-0001.html>
------------------------------
Message: 2
Date: Sun, 10 Jul 2016 00:22:54 +0200
From: Norbert Melzer <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Haskell laziness and data structures.
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Ford writes:
> I am trying to implement ant colony optimization algorithm (or any
> other similar simulation) . In procedural language I would keep the
> world map in 2D matrix that provides O(1) collision check and O(1) ant
> position change.
I do not know that particular algorithm, but most algorithms are even
written down imperatively. First check if odd, iff so do foo and then
repeat first step with next item else repeat step 1 with next item
without doing foo.
In FP the world is working in a slightly different way. FP would say the
above roughly like “for all odd items in a list do foo”
Maybe the difference is not that obvious right now.
But trying to repostulate the wording of an algorithm from imperative
style to declarative style, does help a lot very often.
As I already said, when I think to need mutable datastructures, most of
the time my algorithm is not declarative enough.
Try to reach for a different algorithm which has the same goal, or at
least try to rethink the one you currently have.
> (The memory usage is also important.)
It is always, but it is also very hard to reason about memory usage in
GC'd languages. You might be able to reason about pure allocations while
assuming that garbage is collected instantly, but this is just not true.
Sometimes even immutable stuff is changed in place, just because the
runtime knows that the old value will never be used again. And this does
massively depends on the optimisation, the compiler and the runtime used.
> Thank you for any tips.
>
> King regards,
>
> Ford
>
> Odesláno z BlueMail
>
>
>
> 7. 7. 2016 11:40 AM, 11:40 AM, Norbert Melzer <[email protected]> napsal/a:
>>
>>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.
>>_______________________________________________
>>Beginners mailing list
>>[email protected]
>>http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 97, Issue 9
****************************************
