take-to-first & partition-when

[Greg Fodor]

Hi there, I am just learning Clojure and am processing some BER
encoded integer values. Basically, the most significant bit of the
integer in the stream indicates the split point between integers, and
so I was looking into partition-by to see if that would help. Turns
out, what I really need are two complementary functions: take-to-first
and partition-when. Take-to-first is similar to take-while, but is
*inclusive* and also inverts the boolean. For example:

Clojure=> (take-to-first even? [1 1 1 1])
(1 1 1 1)
Clojure=> (take-to-first even? [1 1 1 1 2 3 3 3])
(1 1 1 1 2)
Clojure=> (take-to-first even? [2 2 2 ])
(2)

Additionally, partition-when runs through the seq and partitions it on
demand when a predicate is true. (Leaving the entry where it is seen
to be true in the current partition:

Clojure=> (partition-when even? [1 1 1 2 3 3 3 4 3 3 3 4 3 3 3])
((1 1 1 2) (3 3 3 4) (3 3 3 4) (3 3 3))
Clojure=> (partition-when even? [1 1 1])
((1 1 1))
Clojure=> (partition-when even? [1 1 1 2 3 3 3])
((1 1 1 2) (3 3 3))
Clojure=> (partition-when even? [2 2 2 2])
((2) (2) (2) (2))

These seem to sit aside the current take and partitioning functions
since they are basically looking at an truth value that indicates a
partition or stopping event that we want to capture and cease moving
forward. Here is the source:

(defn take-to-first
"Returns a lazy sequence of successive items from coll up to
and including the point at which it (pred item) returns true.
pred must be free of side-effects."
[pred coll]
(lazy-seq
(when-let [s (seq coll)]
(if-not (pred (first s))
(cons (first s) (take-to pred (rest s)))
(list (first s))))))

(defn partition-when
"Applies f to each value in coll, splitting it each time f returns
true. Returns a lazy seq of lazy seqs."
[f coll]
(when-let [s (seq coll)]
(let [run (take-to-first #(f %) s)
res (drop (count run) s)]
(lazy-seq
(cons run (partition-when f res))))))

I think these could make a good addition to clojure.contrib.seq.
Please let me know if there is an easier way to get this in if you
agree. Also, please let me know if these are the best ways to write
these functions, since I am still a newbie!

[Greg Fodor]

Just saw that I need to sign the contributor agreement. Will do
promptly. I additionally have implemented two new functions that I
believe could fit in clojure-contrib.seq and clojure-
contrib.combinatorics. The seq function partition-at-fenceposts allows
you to partition a seq based upon bits flipped in an integer value
passed in, where 1-bits correspond to partition boundaries, the least
significant bit being earlier fenceposts in the seq. As such, this
makes it possible to easily implement a function named partitions for
clojure-contrib.combinatorics, which yields a lazy seq of all possible
partitions of a seq.

user=> (partition-at-fenceposts 1 '(1 2 3 4 5))
((0) (1 2 3 4))

user=> (partition-at-fenceposts 2 '(1 2 3 4 5))
((0 1) (2 3 4))

user=> (partition-at-fenceposts 3 '(1 2 3 4 5))
((0) (1) (2 3 4))

user=> (partitions '(1 2 3))
(((0 1 2)) ((0) (1 2)) ((0 1) (2)) ((0) (1) (2)))

user=> (partitions '(1 2 3 4 5))
(((0 1 2 3 4)) ((0) (1 2 3 4)) ((0 1) (2 3 4)) ((0) (1) (2 3 4)) ((0 1
2) (3 4)) ((0) (1 2) (3 4)) ((0 1) (2) (3 4)) ((0) (1) (2) (3 4)) ((0
1 2 3) (4)) ((0) (1 2 3) (4)) ((0 1) (2 3) (4)) ((0) (1) (2 3) (4))
((0 1 2) (3) (4)) ((0) (1 2) (3) (4)) ((0 1) (2) (3) (4)) ((0) (1) (2)
(3) (4)))

implementation:

(defn take-to-first
"Returns a lazy sequence of successive items from coll up to
and including the point at which it (pred item) returns true.
pred must be free of side-effects."
[pred coll]
(lazy-seq
(when-let [s (seq coll)]
(if-not (pred (first s))

(cons (first s) (take-to-first pred (rest s)))
(list (first s))))))

(defn partition-when
"Applies f to each value in coll, splitting it each time f returns
true. Returns a lazy seq of lazy seqs."
[f coll]
(when-let [s (seq coll)]

(lazy-seq
(let [run (take-to-first f s)

res (drop (count run) s)]

(cons run (partition-when f res))))))

(defn partition-at-fenceposts [b coll]
"Partitions coll at fenceposts corresponding to bits in b that are
set to 1. Returns a lazy seq of lazy seqs."
(let [bits b]
(map #(map first %)
(partition-when
(fn [[i v]] (not (zero? (bit-and (bit-shift-left 1 i)
bits))))
(indexed coll)))))

(defn partitions [coll]
"Returns a lazy seq of possible partitions of coll."
(map #(partition-at-fenceposts % coll) (range (expt 2 (- (count
coll) 1)))))

[Sean Devlin]

Hey Greg, welcome to Clojure :)

You might want to take a look at c.c.seq-utils and the clojure cheat
sheet. Both of these already exist. See take-while & partition-by

The cheat sheet can be found here:
http://clojure.org/cheatsheet

[Greg Fodor]

Hey thanks :) These are different than partition-by and take-while.

partition-by triggers a new partition when the predicate value
*changes*, whereas partition-when triggers a new partition at any
point in the sequence where the predicate is true. take-while takes
all the items up to the point in the sequence where the predicate is
true, where take-to-first does the same but *inclusively*, retaining
the item at which the predicate first becomes true. I'm not sure but I
believe it is not trivial to use partition-by and take-while to
implement either of these.

[Per Vognsen]

That implementation of partitions feels really low level. If you
implement the monadic version of partition-when (which I call
partition-where in my own code), it looks as simple as this:

(defn partitions [xs]
(run-seq (m-partition-where (const [false true]) xs)))

-Per

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

[Garth Sheldon-Coulson]

Hi Greg,

Welcome to Clojure!

I haven't scrutinized your code, but at a glance it looks like your implementations are very idiomatic.

It also seems right to me that these functions can't be implemented directly in terms of take-while and partition-by. Without more thought I can't say if there are more direct implementations than yours, but I wanted to compliment you anyway on getting your hands dirty. These look like useful functions. Perhaps someone
who knows c.c.seq well can say more.

Here's another implementation of take-to-first, just for comparison's sake. I tried to use the standard sequence functions. Yours is twice as fast and more readable.

(defn take-to-first [pred coll]
  (if (seq coll)
    (map last
         (take-while (comp (complement pred) first)
                     (cons (list (first coll)) (partition 2 1 coll))))
    (lazy-seq)))

Garth