4 ms·

Do you know of a good resource for reading about their data-structures, especially anything Haskell doesn't have?

by tome 9y ago

DigitalJack 9y ago
Any book on clojure and website too will go over them. They are fundamental to using clojure. I don't know enough about haskell to say what it does or doesn't have in relation to clojure. However, it's not simply the data structures, but how the language is built to interact with them from a programmers perspective. From a user interface to the language point of view, I find the ways of interacting with maps to be very nice. In particular the dual purpose of "keywords" to serve both as a good index/key in said hash maps, but also as callable look up function for the same key in a hash map leads to simplified code. This, coupled with the extremely high usage of those maps in typical clojure code, makes a big difference. To expand on that a little, "keywords" are symbols that begin with a colon, which I believe is the same as common lisp. :for :example :this :is :a :sentence :of :keywords. They are commonly used as the key in a map. Which has a literal syntax like (def map1 {:a 1 :b 2 :c "taco"}). To pull a value out, you can evaluate (:c map1) which will return "taco". They are hash maps based on work by Philip Bagwell, and I think a lot of languages have versions of this now. At least scheme and Common Lisp do. But I don't believe they have the nice literal syntax and interaction syntax. Many Lisp traditionalists are bothered by the use of curly braces for maps and square brackets for vectors, however I'm a fan. Without this bit of syntax, you have to add verbosity to the language to differentiate defining a map from doing a lookup, etc. For resources, Clojure for the Brave and True is pretty popular. Also the online community is quite friendly, although I have noticed some trends toward "the one true way" of doing things that puts me off a little.
- flavio81 9y ago
  > Many Lisp traditionalists are bothered by the use of curly braces for maps and square brackets for vectors, however I'm a fan. Without this bit of syntax, you have to add verbosity to the language to differentiate defining a map from doing a lookup, etc. I agree with you, in the sense that they are useful, however the complain of "Lisp traditionalists" will be that in any case, if you need them, you can add them to Common Lisp by using reader macros. So in CL the curly braces and brackets are "free" to be used (i.e. define what they should do) in any way you want; on Clojure they are already taken, so it feels a bit uncomfortable.
- madmax96 9y ago
  >Many Lisp traditionalists are bothered by the use of curly braces for maps and square brackets for vectors I have definitely seen this. I'm not sure that I understand this sentiment. The only thing that Clojure is missing is the "system" feel that Common Lisp provides, with things like character macros, symbol macros, etc. That being said, I definitely appreciate how thought through Clojure is, especially when compared to CL. Several things are missing/don't feel well thought out in CL (notion of a `calleable` type is gone, `nth` isn't defined on vectors or strings (but you can still `length` them!) nor is `first` and `rest`) That provides a great deal of friction.
  - kbp 9y ago
    > notion of a `calleable` type is gone You can do this using the metaobject protocol and defining a class with a metaclass of FUNCALLABLE-STANDARD-CLASS, for example, given: (defclass c () ((x :initarg :x :accessor x)) (:metaclass funcallable-standard-class)) (defmethod initialize-instance :after ((c c) &key) (with-slots (x) c (set-funcallable-instance-function c #'(lambda () (format t "~&I'm #~a" x))))) Then (funcall (make-instance 'c :x 3)) will print "I'm #3". > `nth` isn't defined on vectors or strings (but you can still `length` them!) ELT in Common Lisp is generic over sequence types. NTH is specific to lists. If you want to write a function that is generic over sequences, use ELT. If you know that you have a list or an array, and you're writing something performance sensitive, you can avoid type dispatch overhead by using NTH or AREF instead of ELT. > nor is `first` and `rest` You can avoid that friction a lot of the time by writing in terms of MAP, REDUCE, REMOVE-IF-NOT, and so on, as well as LENGTH and ELT, which are all generic over sequences, or doing (iter (for x in-sequence sequence) ...) or whatever. But if you really want to use FIRST and REST to walk through a vector, you can do (coerce vector 'list) first to convert it. Coercing a list to list will just return that list, so that version would work for either, too. I admit, there's no real reason I know of (aside from lack of demand) that there isn't a predefined function like: (defun vector-rest (vector) (make-array (1- (length vector)) :displaced-to vector :displaced-index-offset 1)) Then if it bothered you you could do something like (defun head (sequence) (elt sequence 0)) (defun tail (sequence) (etypecase sequence (list (rest sequence)) (vector (vector-rest sequence))))
- kazinator 9y ago
  > To pull a value out, you can evaluate (:c map1) which will return "taco". Not (map1 :c)? A bit odd.
  - DigitalJack 9y ago
    Both work I believe, but the idiomatic way is keyword first.
wging 9y ago
Here is a good resource on Clojure's persistent vector type: http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-...
mej10 9y ago
Hash Array Mapped Tries are what underly the default maps in Clojure: http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf They are pretty amazing. Of course there are implementations in Haskell now, but the reason they are especially cool in Clojure is how well they integrate with the language and its other features.
- jasonkostempski 9y ago
  I think Bitmapped Vector Trie [1] might be some novelty introduced by Clojure. [1] https://stackoverflow.com/questions/8844707/how-is-a-bitmapped-vector-trie-faster-than-a-plain-vector https://stackoverflow.com/questions/8844707/how-is-a-bitmapp...
KirinDave 9y ago
Folks have linked you to the paper and mentioned tutorials. You might also Okasaki's Purely Functional Data Structures, which ends up in the citations for a lot of these.
- arximboldi 9y ago
  Okasaki's work is really interesting, and it is quite mind-blowing the theoretical properties he achieves by exploiting laziness and so on. At the same time: those data-structures have one fundamental flaws they have high constant factors, specially outside of Haskell. That was Phil Bagwell + Rich Hickey revolutionary contribution in my opinion... finding data-structures that are rather simple yet but work well in practice because they make the right engineering trade-offs and work well with CPU caches, etc.
robto 9y ago
Here's a blog post[0] from the guy who implemented Lean Hash-Array Mapped Trie (HAMT) maps for clojurescript. It's really cool stuff! [0] https://bendyworks.com/blog/leveling-clojures-hash-maps https://bendyworks.com/blog/leveling-clojures-hash-maps
arximboldi 9y ago
Search "Phil Bagwell", most of his papers are quite interesting. If you allow me another shameless plug, I also compiled a good bunch of references in the "Related Work" section of my own paper on immutable vectors: https://public.sinusoid.es/misc/immer/immer-icfp17.pdf https://public.sinusoid.es/misc/immer/immer-icfp17.pdf

Do you know of a good resource for reading about their data-structures, especially anything Haskell doesn't have?

by tome 9y ago

Do you know of a good resource for reading about their data-structures, especially anything Haskell doesn't have?

Any book on clojure and website too will go over them. They are fundamental to using clojure. I don't know enough about haskell to say what it does or doesn't have in relation to clojure. However, it's not simply the data structures, but how the language is built to interact with them from a programmers perspective. From a user interface to the language point of view, I find the ways of interacting with maps to be very nice. In particular the dual purpose of "keywords" to serve both as a good index/key in said hash maps, but also as callable look up function for the same key in a hash map leads to simplified code. This, coupled with the extremely high usage of those maps in typical clojure code, makes a big difference. To expand on that a little, "keywords" are symbols that begin with a colon, which I believe is the same as common lisp. :for :example :this :is :a :sentence :of :keywords. They are commonly used as the key in a map. Which has a literal syntax like (def map1 {:a 1 :b 2 :c "taco"}). To pull a value out, you can evaluate (:c map1) which will return "taco". They are hash maps based on work by Philip Bagwell, and I think a lot of languages have versions of this now. At least scheme and Common Lisp do. But I don't believe they have the nice literal syntax and interaction syntax. Many Lisp traditionalists are bothered by the use of curly braces for maps and square brackets for vectors, however I'm a fan. Without this bit of syntax, you have to add verbosity to the language to differentiate defining a map from doing a lookup, etc. For resources, Clojure for the Brave and True is pretty popular. Also the online community is quite friendly, although I have noticed some trends toward "the one true way" of doing things that puts me off a little.

flavio81 9y ago
> Many Lisp traditionalists are bothered by the use of curly braces for maps and square brackets for vectors, however I'm a fan. Without this bit of syntax, you have to add verbosity to the language to differentiate defining a map from doing a lookup, etc. I agree with you, in the sense that they are useful, however the complain of "Lisp traditionalists" will be that in any case, if you need them, you can add them to Common Lisp by using reader macros. So in CL the curly braces and brackets are "free" to be used (i.e. define what they should do) in any way you want; on Clojure they are already taken, so it feels a bit uncomfortable.
madmax96 9y ago
>Many Lisp traditionalists are bothered by the use of curly braces for maps and square brackets for vectors I have definitely seen this. I'm not sure that I understand this sentiment. The only thing that Clojure is missing is the "system" feel that Common Lisp provides, with things like character macros, symbol macros, etc. That being said, I definitely appreciate how thought through Clojure is, especially when compared to CL. Several things are missing/don't feel well thought out in CL (notion of a `calleable` type is gone, `nth` isn't defined on vectors or strings (but you can still `length` them!) nor is `first` and `rest`) That provides a great deal of friction.
- kbp 9y ago
  > notion of a `calleable` type is gone You can do this using the metaobject protocol and defining a class with a metaclass of FUNCALLABLE-STANDARD-CLASS, for example, given: (defclass c () ((x :initarg :x :accessor x)) (:metaclass funcallable-standard-class)) (defmethod initialize-instance :after ((c c) &key) (with-slots (x) c (set-funcallable-instance-function c #'(lambda () (format t "~&I'm #~a" x))))) Then (funcall (make-instance 'c :x 3)) will print "I'm #3". > `nth` isn't defined on vectors or strings (but you can still `length` them!) ELT in Common Lisp is generic over sequence types. NTH is specific to lists. If you want to write a function that is generic over sequences, use ELT. If you know that you have a list or an array, and you're writing something performance sensitive, you can avoid type dispatch overhead by using NTH or AREF instead of ELT. > nor is `first` and `rest` You can avoid that friction a lot of the time by writing in terms of MAP, REDUCE, REMOVE-IF-NOT, and so on, as well as LENGTH and ELT, which are all generic over sequences, or doing (iter (for x in-sequence sequence) ...) or whatever. But if you really want to use FIRST and REST to walk through a vector, you can do (coerce vector 'list) first to convert it. Coercing a list to list will just return that list, so that version would work for either, too. I admit, there's no real reason I know of (aside from lack of demand) that there isn't a predefined function like: (defun vector-rest (vector) (make-array (1- (length vector)) :displaced-to vector :displaced-index-offset 1)) Then if it bothered you you could do something like (defun head (sequence) (elt sequence 0)) (defun tail (sequence) (etypecase sequence (list (rest sequence)) (vector (vector-rest sequence))))
kazinator 9y ago
> To pull a value out, you can evaluate (:c map1) which will return "taco". Not (map1 :c)? A bit odd.
- DigitalJack 9y ago
  Both work I believe, but the idiomatic way is keyword first.

wging 9y ago

Here is a good resource on Clojure's persistent vector type: http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-...

mej10 9y ago

Hash Array Mapped Tries are what underly the default maps in Clojure: http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf They are pretty amazing. Of course there are implementations in Haskell now, but the reason they are especially cool in Clojure is how well they integrate with the language and its other features.

jasonkostempski 9y ago
I think Bitmapped Vector Trie [1] might be some novelty introduced by Clojure. [1] https://stackoverflow.com/questions/8844707/how-is-a-bitmapped-vector-trie-faster-than-a-plain-vector https://stackoverflow.com/questions/8844707/how-is-a-bitmapp...

KirinDave 9y ago

Folks have linked you to the paper and mentioned tutorials. You might also Okasaki's Purely Functional Data Structures, which ends up in the citations for a lot of these.

arximboldi 9y ago
Okasaki's work is really interesting, and it is quite mind-blowing the theoretical properties he achieves by exploiting laziness and so on. At the same time: those data-structures have one fundamental flaws they have high constant factors, specially outside of Haskell. That was Phil Bagwell + Rich Hickey revolutionary contribution in my opinion... finding data-structures that are rather simple yet but work well in practice because they make the right engineering trade-offs and work well with CPU caches, etc.

robto 9y ago

Here's a blog post[0] from the guy who implemented Lean Hash-Array Mapped Trie (HAMT) maps for clojurescript. It's really cool stuff! [0] https://bendyworks.com/blog/leveling-clojures-hash-maps https://bendyworks.com/blog/leveling-clojures-hash-maps

arximboldi 9y ago

Search "Phil Bagwell", most of his papers are quite interesting. If you allow me another shameless plug, I also compiled a good bunch of references in the "Related Work" section of my own paper on immutable vectors: https://public.sinusoid.es/misc/immer/immer-icfp17.pdf https://public.sinusoid.es/misc/immer/immer-icfp17.pdf