algorithms

8.12

algorithms🔗ℹ

Conor Hoekstra

(require algorithms)

package: algorithms

A package containing many useful algorithms (borrowed from many other programming languages).

There is a GNU Guile scheme version of this package.

procedure
(adjacent-map proc lst) → (listof any/c)
proc : (-> any/c any/c any/c)
lst : list?

This algorithm is similar to Haskell’s mapAdjacent.

Returns a list of elements after apply proc to adjacent elements.

Examples:

> (adjacent-map * '(1 2 3 4 5 6))
'(2 6 12 20 30)
> (adjacent-map < '(1 2 1 3 4 3))
'(#t #f #t #t #f)

procedure
(all? lst) → (boolean?)
lst : (listof boolean?)

This algorithm is similar to Python’s all.

Returns #t if all the elements of lst are #t, otherwise returns #f.

Examples:

> (all? '(#t #t #t))
#t
> (all? '(#t #t #f))
#f

procedure
(any? lst) → (boolean?)
lst : (listof boolean?)

This algorithm is similar to Python’s any.

Returns #t if any of the elements of lst are #t, otherwise returns #f.

Examples:

> (any? '(#f #t #f))
#t
> (any? '(#f #f #f))
#f

procedure
(chunk-by pred lst) → list?
pred : (-> any/c any/c boolean?)
lst : list?

This algorithm is similar to C++’s chunk_by_view.

Takes a binary predicate pred and a list lst, and partitions lst into sublists (chunks) based on the predicate. The list is split between each pair of adjacent elements for which pred returns #f. The first element of each such pair belongs to the current chunk, and the second element starts the next chunk.

Examples:

> (chunk-by eq? '(1 1 3 2 2))
'((1 1) (3) (2 2))
> (chunk-by < '(1 2 1 3 4 3))
'((1 2) (1 3 4) (3))

procedure
(chunks-of lst k) → (listof list?)
lst : list?
k : exact-nonnegative-integer?

This algorithms is the same as Haskell’s chunksOf. and similar to Python’s itertools.batched

Returns a list of lists of k elements each. Note that this is a specialization of sliding where size is equal to step.

Examples:

> (chunks-of '(1 2 1 3 4 3) 2)
'((1 2) (1 3) (4 3))
> (chunks-of '(1 2 1 3 4 3) 3)
'((1 2 1) (3 4 3))

procedure
(generate n proc) → (listof any/c)
n : exact-nonnegative-integer?
proc : (-> any/c)

This algorithm is similar to C++’s generate.

Returns a list of n elements generated from invoking proc n times.

Examples:

> (generate 3 *)
'(1 1 1)
> (generate 3 +)
'(0 0 0)

procedure
(increasing? lst) → (boolean?)
lst : (listof real?)

Returns #t if all the elements of lst are strictly increasing, otherwise returns #f.

Examples:

> (increasing? '(1 2 3 4))
#t
> (increasing? '(1 2 3 5))
#t
> (increasing? '(1 2 2 3))
#f

procedure
(init lst) → list?
lst : list?

This algorithm comes from Haskell’s init.

Return all the elements of a list except the last one.

Examples:

> (init '(1 2 3 4))
'(1 2 3)
> (init '((1 2) (3 4) (5 6)))
'((1 2) (3 4))

procedure
(juxt proc ...) → procedure?
proc : (procedure?)

This algorithm comes from Clojure’s juxt.

Takes variable number of procedures and returns a procedure that is the juxtaposition of those procedures. The returned procedure takes a variable number of arguments, and returns a list containing the result of applying each procedures to the arguments.

Examples:

> ((juxt first last) '(1 2 3))
'(1 3)
> ((juxt + *) 1 2 3 4)
'(10 24)
> ((juxt zip append) '(1 2 3) '(4 5 6))
'(((1 4) (2 5) (3 6)) (1 2 3 4 5 6))

procedure
(product lst) → real?
lst : (listof real?)

Returns the product of the elements in lst.

Examples:

> (product '(1 2 3))
6
> (product '(1 2 3 4))
24

procedure
(repeat n val) → list?
n : exact-nonnegative-integer?
val : any/c?

This algorithms is the same as Clojures’s repeat and D’s repeat.

Returns a list of val repeated n times.

Examples:

> (repeat 5 #t)
'(#t #t #t #t #t)
> (repeat 5 '())
'(() () () () ())

procedure
(replicate lst lst2) → list?
lst : (listof exact-nonnegative-integer?)
lst2 : list?

This algorithms is the similar to APL’s replicate.

Returns a list of of the lst2 values each repeated n times where n is the corresponding element in lst.

Examples:

> (replicate '(1 0 1) '(a b c))
'(a c)
> (replicate '(0 1 2) '(a b c))
'(b c c)

procedure
(scanl lst) → list?
lst : list?

This algorithm originally comes from APL’s monadic \ scan operator. It is more similar to Haskell’s scanl1 however.

scanl is similar to foldl, but returns a list of successive reduced values from the left.

Examples:

> (scanl + '(1 2 3 4))
'(1 3 6 10)
> (scanl * '(1 2 3 4))
'(1 2 6 24)

procedure
(scanr lst) → list?
lst : list?

This algorithm originally comes from APL’s monadic \ scan operator. It is more similar to Haskell’s scanr1 however.

scanr is similar to foldr, but returns a list of successive reduced values from the right.

Examples:

> (scanr + '(1 2 3 4))
'(10 9 7 4)
> (scanr * '(1 2 3 4))
'(24 24 12 4)

procedure
(sliding lst size [step]) → (listof list?)
  lst : list?
  size : exact-nonnegative-integer?
  step : exact-nonnegative-integer? = 1

This algorithm is the same as Haskell’s divvy, Clojure’s partition and D’s slide.

Returns a list of lists of size elements each, at offset step apart.

step has to be equal to or smaller than length of the lst.

Examples:

> (sliding '(1 2 3 4) 2)
'((1 2) (2 3) (3 4))
> (sliding '(1 2 3 4 5) 2 3)
'((1 2) (4 5))
> (sliding '(1 2) 2 2)
'((1 2))

procedure
(sorted? lst) → (boolean?)
lst : list?

This algorithm is similar to C++’s std::is_sorted.

Returns #t if all the elements of lst are in sorted order, otherwise returns #f.

Examples:

> (sorted? '(1 2 3 4))
#t
> (sorted? '(1 2 3 3))
#t
> (sorted? '(1 2 3 2))
#f

procedure
(sum lst) → real?
lst : (listof real?)

Returns the sum of the elements in lst.

Examples:

> (sum '(1 2 3 4))
10
> (sum '())
0

procedure
(tail lst) → list?
lst : list?

This algorithm comes from Haskell’s tail.

Return all the elements of a list except the first one.

Note: this is the same as Racket’s cdr and rest and therefore isn’t really necessary.

Examples:

> (tail '(1 2 3))
'(2 3)
> (tail '(1))
'()

procedure
(zip lst ...) → (listof list?)
lst : list?

This algorithm is similar to Haskell’s zip and Python’s zip.

Returns a list of lists of elements from each of lists passed to the procedure.

Another way to think of zip is that it turns rows into columns, and columns into rows. This is similar to transposing a matrix.

Examples:

> (zip '(1 2 3) '(4 5 6))
'((1 4) (2 5) (3 6))
> (zip '() '())
'()
> (zip '(0 1) '(2 3) '(5 7))
'((0 2 5) (1 3 7))

procedure
(zip-with proc lst ...) → (listof any/c)
proc : (-> any/c ... any/c)
lst : list?

This algorithm is similar to Haskell’s zipWith.

Returns a list after zipping together the variadic number of lsts and applying proc to each of the "zipped together" elements.

Examples:

> (zip-with + '(1 2 3) '(4 5 6))
'(5 7 9)
> (zip-with + '(1 2 3) '(4 5 6) '(7 8 9))
'(12 15 18)