Remove-first function

[nickikt]

Hallo all,

I'm working trough Essentials of Programming Languages. I'm trying to
right a function like this one:

(defn scheme-remove-first [syb lst]
(if (empty? lst)
'()
(if (= (first lst) syb)
(rest lst)
(cons (first lst) (scheme-remove-first syb (rest lst))))))

in a idiomatic clojure way (this is just a scheme to clojure 1:1
version). I don't like that this function produces stack overflows.

I tried some stuff but I it (almost) semantically correct working but
I didn't like my code. Can anyone come up with a good version?

[Randy Hudson]

Here's my take:

(defn remove-first [x coll]
(let [[pre post] (split-with #(not= x %) coll)]
(concat (pre (rest post))))

[Andrew Boekhoff]

Hi,

One way to prevent the stack overflows is to wrap it in a lazy seq.
For example:

(defn remove-first [x coll]
(lazy-seq
(when (seq coll)
(let [[y & ys] coll]
(if (= target y)
ys
(cons y (remove-first x ys)))))))

[Mark Engelberg]

The simplest translation is to wrap a lazy-seq around the last line to
avoid the stack overflows.

On Sat, Jul 24, 2010 at 8:41 AM, nickikt <nic...@gmail.com> wrote:
> (defn scheme-remove-first [syb lst]
>  (if (empty? lst)
>    '()
>    (if (= (first lst) syb)
>      (rest lst)
>      (cons (first lst) (scheme-remove-first syb (rest lst))))))

becomes

(defn scheme-remove-first [syb lst]
(if (empty? lst)
'()
(if (= (first lst) syb)
(rest lst)

(lazy-seq (cons (first lst) (scheme-remove-first syb (rest lst)))))))

Also, you can omit the ' in front of the () if you like.

[Mark Engelberg]

On Sat, Jul 24, 2010 at 11:45 AM, Mark Engelberg
<mark.en...@gmail.com> wrote:
> The simplest translation is to wrap a lazy-seq around the last line to
> avoid the stack overflows.

Just to clarify, there are at least three reasonable places to place
the call to lazy-seq. You can put lazy-seq around the full body of
the function. You can place it around the cons. You can place it
around the recursive call to scheme-remove-first. Each choice results
in slightly different laziness behavior, i.e., when various elements
are computed, but the overall semantics of the sequence remains the
same and stack overflows will be avoided. Placing the lazy-seq around
the recursive function call will cause scheme-remove-first to compute
the first element right away, and delay the rest. Placing the
lazy-seq around the full body will prevent any computation until it is
asked for by a consumer. Placing the lazy-seq around the cons results
in in immediate behavior for the nil and
removable-item-at-front-of-list case, and delayed behavior otherwise.
All are acceptable choices, but preferences vary. Probably placing
lazy-seq around the full body is the most common style you'll see in
Clojure, although I tend to place it where the laziness is actually
required (like around the recursive call, or around the cons).

You've probably noticed from the other samples posted that many
Clojurians prefer to use (seq lst) instead of (not (empty? lst)), and
organize their code around the not-empty case.

So (if (empty? lst) empty-case not-empty-case) becomes (if (seq lst)
not-empty-case empty-case)

When the empty case also results in nil, you can replace the if
structure with a one-armed when, because when automatically returns
nil in the other case.

So (if (seq lst) not-empty-case nil) becomes (when (seq lst) not-empty-case).

[ataggart]

To add one small addendum to Mark's excellent comment, if you use lazy-
seq then you don't need to worry about the nil from when

On Jul 24, 12:01 pm, Mark Engelberg <mark.engelb...@gmail.com> wrote:
> On Sat, Jul 24, 2010 at 11:45 AM, Mark Engelberg
>

[nickikt]

@Randy Hudson
Really like that solution.

@Mark Engelberg
Thanks for the explanation

[Gary Fredericks]

Well obviously if you can get something to be tail-recursive you won't have the stack overflows, and the thing in your code that prevents tail recursion is having to cons the result of the recursive call. So let's try this:

(defn remove-first
  [syb lst]
  (let [[before after]
          (loop [b [] a lst]
            (if (empty? lst)
              [b a]
              (if (= syb (first a))
                [b (rest a)]
                (recur (cons (first a) b) (rest a)))))]
   (concat (reverse before) after)))

user=> (remove-first 4 '(1 5 3 4 2 6 674 4 2))
(1 5 3 2 6 674 4 2)

I'm interested if somebody comes up with something more efficient, i.e. that doesn't require the reversal.

Gary

--
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

--
Gary Fredericks
(660)-623-1095
frederi...@gmail.com
www.gfredericks.com

[Mark Engelberg]

On Sat, Jul 24, 2010 at 9:07 AM, Gary Fredericks
<frederi...@gmail.com> wrote:
> (defn remove-first
>   [syb lst]
>   (let [[before after]
>           (loop [b [] a lst]
>             (if (empty? lst)
>               [b a]
>               (if (= syb (first a))
>                 [b (rest a)]
>                 (recur (cons (first a) b) (rest a)))))]
>    (concat (reverse before) after)))
>
> user=> (remove-first 4 '(1 5 3 4 2 6 674 4 2))
> (1 5 3 2 6 674 4 2)
>
> I'm interested if somebody comes up with something more efficient, i.e. that
> doesn't require the reversal.

If you change (cons (first a) b) to (conj b (first a), then no
reversal will be required.

[Mark Engelberg]

I expanded on this theme in a blog post:
http://programming-puzzler.blogspot.com/2010/07/translating-code-from-python-and-scheme.html