[Haskell-beginners] Haskell laziness and data structures.

[Ford]

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 <timmelzer at gmail.com> 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
>Beginners at haskell.org
>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.html>