[Haskell-beginners] Re: Haskell data structures: cheap immutable manipulation and nested equality?

[Heinrich Apfelmus]

Anand Patil wrote:
> - Cheap 'manipulation'. In the following:
> 
> user=> (def m {:a 1 :b 2})
> #'user/m1
> user=> (assoc m :a 3)
> {:a 3, :b 2}
> 
> the 'assoc' function produces a new map which actually shares
> structure with m, meaning it doesn't need to make a full copy in
> memory; but it also leaves m unchanged. This works efficiently even
> for nested, mixed collections.

Since Haskell is pure, this is the default. Every data structure is
persistent and shares as much as possible with previous versions.
Example in point: an infinite list of ones

   ones = 1:ones


> - Cheap equality by value:
> 
> user=> (= m {:a 1 :b 2 :c {:d 3 :f 4}})
> false
> user=> (= m {:a 1 :b 2})
> true
> 
> If I understand correctly, equality is computed based on some kind of
> hash rather than by comparing the two maps element by element, so it's
> efficient even for large and/or nested collections.
> 
> Do Haskell's data structures have analogous properties? If not, are
> there libraries providing such data structures?

Not present in Haskell, no existing library either. You can roll your
own, of course. (Also note that hash based comparison might yield false
positives).

Why would you need this feature? I can only think of common
subexpression elimination.


Generally, the above two points are minor compared to the other things
that Haskell has to offer, like pattern matching, Hindler Milner type
system, purity.


Regards,
apfelmus

--
http://apfelmus.nfshost.com