CODEWITHSUNDEEP
clojurereverse
Ramy
Ramy

Reputation: 21261

reversing sequences without standard libraries in Clojure

I'm trying to go through the problem set at 4clojure.org. I'm on number 23 (reverse a string without using 'reverse' function). I'm getting this error:

Don't know how to create ISeq from: java.lang.Long

here's my code:

(fn rev [coll] 
  (if (= () coll)
    nil
    ((cons(rev (rest coll))(first coll)))))

edited now to this:

(fn rev [coll] 
  (if (empty? coll)
    coll
    (concat(rev (rest coll))((list first coll)))))

presumably this is from trying to cons the head of the sequence to the end of the rest of the sequence.

What's the right way of doing this?

Upvotes: 2

Views: 803

Answers (3)

Suz
Suz

Reputation: 3802

Like the OP, I've become frustrated trying to construct recursive solutions with when-let and if, next and last, etc, etc. So now I'm trying to understand @ntalbs answer and see if I can take this further, studying the Clojure documentation at http://clojuredocs.org/quickref/Clojure%20Core.

Part #1 -- Observations:
cons is a function of lists, whereas conj is a generic function of collections, and concat is listed under 'Use(modification)' of sequences, but it returns a Lazy Sequence. So how do these things differ in practice?

  1. Argument order matters: you can't conj a value and a sequence, only a sequence and a value. For cons it's the other way around. concat appears to be more forgiving.

    user=> (type (conj 1 '(2 3 4 5)))
ClassCastException java.lang.Long cannot be cast to clojure.lang.IPersistentCollection  clojure.core/conj (core.clj:83)
user=> (type (cons '(2 3 4 5) 1))
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long  clojure.lang.RT.seqFrom (RT.java:505)

  2. Three different return types: Cons, PersistentList or LazySeq

    user=> (type (cons 1 '(2 3 4 5)))
clojure.lang.Cons
user=> (type (conj '(2 3 4 5) 1))
clojure.lang.PersistentList
user=> (type (concat 1 '(2 3 4 5)))
clojure.lang.LazySeq

  3. Different behaviour for different types of collections:

    user=> (cons 3 (sorted-set 5 7 2 7))
(3 2 5 7)     ; type = Cons, 3 is just appended to the list, 
user=> (conj (sorted-set 5 7 2 7) 3)
#{2 3 5 7}    ; type = PersistentTreeSet, with 3 in the correct position.
user=> (concat 3 (sorted-set 5 7 2 7))   ; LazySeq can't be directly returned, so...(order doesn't matter)
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long  clojure.lang.RT.seqFrom (RT.java:505)

To my mind, conj has the most straightforward behaviour, so I will use this by preference, unless I actually want a lazy sequence or specifically a list.

Part #2 -- @Ramy's 'too dense for me' Understanding @ntalbs's solution.

The description above suggests that conj is the most appropriate method for adding things into a collection, which is exactly what @ntalbs's solution does. The usage for reduce is at http://clojuredocs.org/clojure_core/clojure.core/reduce It's an effective way of applying a function while collecting together the values in a collection. 

(reduce f val coll)

So, reduce will apply f for each member of the collection, starting with val. The call (reduce conj () coll) thus takes the collection and first applies (conj () (first coll)). Then it applies (conj result (second coll)), and (conj result (third coll)), etcetera, where result is the result of the previous step.

reduce looks like a very powerful command.

Part #3 -- yet another solution

(fn rev [coll]
    (into () coll))

From the documentation, into appears to be syntactic sugar for (reduce conj to-coll from-coll). I'm not sure if this is elegant or just dense. It does work, though, with minimal key-strokes.

Upvotes: 1

A. Webb
A. Webb

Reputation: 26446

This error is because you are trying to cons a seq to an element rather than an element to a seq. In other words, your arguments to cons are in the wrong order. But, if you corrected the order, you'd just be piecing a list back together in the same order.

Using the same general idea you have, you could turn the second argument into a list by wrapping it in (list ...) and then concat the two lists together:

(fn rev [coll] 
  (if (empty? coll)
    coll
    (concat
      (rev (rest coll))
      (list (first coll)))))

You'll discover more concise solutions as you go along.

Upvotes: 3

ntalbs
ntalbs

Reputation: 29438

Second argument of cons in clojure should be a sequence, however, (first coll) is not a sequence but an element of a collection. Perhaps you pass the collection of numbers, so (first coll) spit a number (long) and clojure cannot create ISeq from the number.

user=> (doc cons)
-------------------------
clojure.core/cons
([x seq])
  Returns a new seq where x is the first element and seq is
    the rest.

You can implement reverse simply like the following:

(fn rev [coll]
    (reduce conj () coll))

I check the above code and it passed all three test cases in 4clojure site.

Upvotes: 3

Related Questions