Scheme dotted pair equivalent in Clojure

[octopusgrabbus]

I have a need to learn enough scheme to read it and write a few functions. I came across dotted pair notation. I am trying to grok it in terms of the only Lisp I know, Clojure. Does dotted pair notation in Scheme compare to  form in Clojure, and if so, how?

[David Nolen]

Not possible in Clojure and a source of hassle in Scheme and Common Lisp. If you have dotted pairs you can never know if you have a proper list.

David

On Sat, Jun 16, 2012 at 11:35 AM, octopusgrabbus <octopus...@gmail.com> wrote:

I have a need to learn enough scheme to read it and write a few functions. I came across dotted pair notation. I am trying to grok it in terms of the only Lisp I know, Clojure. Does dotted pair notation in Scheme compare to  form in Clojure, and if so, how?

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[octopusgrabbus]

Thanks for answering. I am taking from your answer that I can be Lisp/Clojure-esque in Scheme and not worry about dotted pairs. That is, I can make a grid out of lists, rather than using cons to construct them. That's what I'm trying to do.

[David Nolen]

dotted pairs and cons in Scheme and CL both allow you specify an improper tail. This has some historical utility if you are using cons as a way to build up non-list data structures. Scheme and CL both provide better facilities for data structures than using cons.

As far as I know lists are just conses with proper tails.

David

[Paul Stadig]

On Jun 16, 11:37 am, David Nolen <dnolen.li...@gmail.com> wrote:
> Not possible in Clojure and a source of hassle in Scheme and Common Lisp.
> If you have dotted pairs you can never know if you have a proper list.

I'm probably missing some context, but I've heard this argument before
and had a hard time understanding it. Clojure is dynamically typed,
and you should expect that calling something like 'map with an
improper list would blow up just like you would expect this to blow
up:

user=> (map inc 5)
IllegalArgumentException Don't know how to create ISeq from:
java.lang.Long clojure.lang.RT.seqFrom (RT.java:494)

With dotted pairs I would expect something like:

user=> (map inc '(5 6 . 7)))
IllegalArgumentException Don't know how to create ISeq from:
java.lang.Long clojure.lang.RT.seqFrom (RT.java:494)

And in Racket you get:

> (map (lambda (x) (+ x 1)) 2)
map: expects type <proper list> as 2nd argument, given: 2; other
arguments were: #<procedure>
> (map (lambda (x) (+ x 1)) '(1 . 2))
map: expects type <proper list> as 2nd argument, given: '(1 . 2);
other arguments were: #<procedure>

I'm not necessarily arguing that Clojure should have dotted pairs. I
think something like [1 2] works well as a substitute. Plus Clojure
already uses . for other things and the overloading might be
confusing. I'm just not sure I understand the typing argument for a
dynamically typed language.


Paul

[Mark Engelberg]

A cons is essentially just a struct with two fields.  In Clojure, it's sort of like:

(defrecord Cons [car cdr])
(defn cons [x y] (Cons. x y))
(defn first [x] (:car x))
(defn rest [x] (:cdr x))

The amazing thing is that you can represent any collection of arbitrary length, just by nesting these structs with two fields (aka "cons cells"), e.g., (cons 1 (cons 2 (cons 3 (cons 4 empty))))

But the real magic happens in the printer, where the printer knows to follow the chain of conses until it hits empty and print the whole thing out as a list (1 2 3 4).

In Scheme, there's no restriction on what you can pass to cons.  So you can perfectly legally do (cons 1 2).  How should this print?  By convention, it prints as (1 . 2).  So that's all a dotted pair is.

Why is it used?

Well, the most common use is in map-like structures.  A map is comprised of key-value pairs, so you might as well store these pairs as (cons key value) rather than (cons key (cons value empty)).  The former saves you memory by using only one cons instead of two.  The former prints as a dotted pair, since it is not a valid list ending in empty.

Clojure uses a similar trick to save memory in key-value pairs for maps.

user=> (first {:a 1, :b 2})
[a 1]

Even though it prints like a list, this is really not a true list.  It is Clojure's equivalent of a dotted pair, a class called MapEntry which contains a key and a value.

user=> (type (first {:a 1, :b 2}))
clojure.lang.MapEntry

Note that you can build MapEntry structures directly and access their components, if you want to achieve a similar effect in your own code:

user=> (clojure.lang.MapEntry :a 1)
[:a 1]   ;Prints like a list, but this is not a true list.

user=> (key (clojure.lang.MapEntry. :a 1))
:a

user=> (value (clojure.lang.MapEntry. :a 1))
1

[Mark Engelberg]

In the previous post, I accidentally deleted a dot when pasting:
user=> (clojure.lang.MapEntry :a 1)
should have been
user=> (clojure.lang.MapEntry. :a 1)

[Jonas]

A very nice section of SICP[1] describes how cons/car/cdr can be built only with functions. Translated to Clojure it might look like

    (defn cons [a b]

      #(condp = %

         :car a

         :cdr b))

    (defn car [cons-cell]

      (cons-cell :car))

    (defn cdr [cons-cell]

      (cons-cell :cdr))

    (car (cons :a :b)) => :a

    (cdr (cons 1 2)) => 2

An excellent example of closures and the use of higher order functions.

Pairs can also serve as nice example usage for defprotocol and reify:

    (defprotocol Pair

      (car [cons-cell])

      (cdr [cons-cell]))

    (defn cons [a b]

      (reify Pair

        (car [_] a)

        (cdr [_] b)))

    (car (cons :a :b)) => :a

    (cdr (cons 1 2)) => 2

[1]: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.3