algorithms

8.6

algorithms

Conor Hoekstra

(require algorithms)

package: algorithms

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

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

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
(chunks-of lst k) → (listof list?)
lst : list?
k : exact-nonnegative-integer?

This algorithms is the same as Haskell’s chunksOf.

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
(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 : integer?

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
(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 algorithms 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.

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

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 lst2) → (listof list?)
lst : list?
lst2 : list?

This algorithm is similar to Haskell’s zip.

Returns a list of corresponding pairs when given two lists.

Examples:

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

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)