6 Composing Operations
(require relation/composition) | package: relation-lib |
Generic algebraic operators for composing data.
The built-in operators + and * operate on numbers specifically. Often, however, we are interested in performing operations "similar" to these for datatypes that aren’t numbers, for which we would resort to type-specific operators like append for lists.
This module generalizes the standard algebraic operators to work on any type that supports a "canonical" notion of addition, multiplication, or concatenation. This allows our intuitions about addition and other forms of composition to extend over all appropriate types via the use of the common generic operators +, * and ~. Additionally, a number of general-purpose utilities leveraging generic composition are provided.
6.1 Interfaces
This module provides three generic interfaces – gen:appendable, gen:multipliable, and gen:addable. These are meant to represent the canonical "idea" of the operations of concatenation, multiplication and addition, respectively, whose behavior may be customized for each type via these generic interfaces, and used via the common operators ~ (concatenation), * (multiplication), and + (addition).
In order to support generic composition seamlessly, all of the composition interfaces support a generic (rather than type- and operation-specific) identity value that is employed in cases where type information is not available.
value
ID : composition-identity?
> (+ 5 ID) 5
> (* ID 5) 5
> (+) (composition-identity)
> (apply * '()) (composition-identity)
> (: 3 ID) '(3)
In the event no operands are received in the course of a computation, the result of composition would be ID. While ID implements some generic interfaces that allow it to be treated as a null value in various contexts (such as generic sequences), it would not be a usable result in utilities that are expecting a specific type such as a string. In such cases, the result could be converted to the expected type using one of the transformers in relation/type such as ->string. If you are not using a built-in type but rather a custom type, however, you could use the following more general utility to "reify" the generic identity value to a type of your choosing:
> (reify ID 3) 0
> (reify ID 3 *) 1
> (reify ID "cherry") ""
> (reify ID (list)) '()
> (reify "hi" (list)) "hi"
> (reify '(1 2 3) "") '(1 2 3)
> (some? "") #f
> (some? "abc") #t
> (some? (list 1 2)) #t
> (some? (list)) #f
> (some? empty-stream) #f
> (some? (hash)) #f
> (some? (hash 'a 1)) #t
6.1.1 Concatenation
value
procedure
(appendable? v) → boolean?
v : any/c
> (appendable? 3) #t
> (appendable? #\a) #f
> (appendable? "cherry") #t
> (appendable? (list)) #t
> (appendable? (set)) #t
> (appendable? (hash)) #t
> (appendable? (vector)) #t
To implement this interface for custom types, the following methods need to be implemented, unless the type already implements another interface for which a default implementation exists for gen:appendable (such as gen:sequence) and if more specific handling is not needed for the custom type.
procedure
(append a b) → appendable?
a : appendable? b : appendable?
In addition to providing a definition of concatenation appropriate to the type, implementations of this method must also handle the special value ID in the following way: if the operand b is eq? to ID, then the result of the function must be a.
procedure
a : appendable?
procedure
a : appendable?
Providing an implementation for this method is optional, and most types would usually not define an inverse for an append-like operation. That is, in mathematical terms, append-like operations typically form an algebraic semigroup or monoid rather than a group.
6.1.2 Multiplication
value
Since numbers are the only common type for which the multiply operation is defined, this interface is present mostly for uniformity, being leveraged by utilities like fold, and of course also for use in custom types.
> (* 1 2 3 4) 24
procedure
(multipliable? v) → boolean?
v : any/c
> (multipliable? 3) #t
> (multipliable? #\a) #f
> (multipliable? "cherry") #f
> (multipliable? (list)) #f
To implement this interface for custom types, the following methods need to be implemented:
procedure
(multiply a b) → multipliable?
a : multipliable? b : multipliable?
In addition to providing a definition of multiplication appropriate to the type, implementations of this method must also handle the special value ID in the following way: if the operand b is eq? to ID, then the result of the function must be a.
procedure
a : multipliable?
procedure
a : multipliable?
Providing an implementation for this method is optional; a multiply operation need not admit an inverse, for instance, for a custom integer type, multiplication would not define an inverse since multiplicative inverses for numbers would be rational numbers, rather than integers, thus being excluded by the "same type" requirement above.
6.1.3 Addition
value
> (addable? 3) #t
> (addable? #\a) #f
> (addable? "cherry") #f
> (addable? (list)) #f
> (addable? (set)) #f
> (addable? (hash)) #f
> (addable? (vector)) #t
To implement this interface for custom types, the following methods need to be implemented:
In addition to providing a definition of addition appropriate to the type, implementations of this method must also handle the special value ID in the following way: if the operand b is eq? to ID, then the result of the function must be a.
procedure
(addable-identity a) → addable?
a : addable?
procedure
(addable-inverse a) → addable?
a : addable?
Providing an implementation for this method is required; an addition operation must admit an inverse. That is, in mathematical terms, addition-like operations are expected to form an algebraic group.
6.2 Types
struct
map : (-> any/c any/c) gen : (-> any/c any/c) stop? : (-> any/c boolean?) tail : (-> any/c collection?) cons : (-> any/c collection? collection?)
map - The function that will be applied to each seed value to produce the values of the resulting sequence.
gen - The function that will be applied to each seed value to generate the next seed value.
stop? - The condition applied to the seed value that, when true, terminates the unfold operation. It is specified via the keyword argument #:stop?. If left unspecified, this defaults to false., i.e. the unfold operation does not terminate, and must be used together with a utility like take.
tail - The function that will be applied to the seed value at the point when the unfold operation terminates (or when it begins, in the case of unfoldr), to produce the tail of the resulting sequence. This attribute is typically used to indicate the type of the resulting sequence, and must be provided via the keyword argument #:tail. If left unspecified, it defaults to (thunk* null), that is, a function that returns null, resulting in the output sequence being a list. If a hash is desired instead, for example, this could be specified as (thunk* (hash)).
cons - The constructor to be used in creating the resulting sequence, which is provided via the keyword argument #:cons. If left unspecified, this defaults to the generic type constructor, :, so that the type of the resulting sequence is determined by the type of its tail. This value is used in unfoldl and unfoldr but it is ignored in unfold, which produces values lazily using stream-cons instead.
map and gen are the only parameters that are always required, while stop? is only required for unfoldl and unfoldr, but not for unfold (because the former are not lazy and thus require a finite stop condition). tail is usually needed when the desired output sequence is not a list or a stream, and cons is rarely needed since it can usually be inferred from the tail.
6.3 Utilities
procedure
(~ v ...) → appendable?
v : appendable?
procedure
(.. v ...) → appendable?
v : appendable?
procedure
(∘ v ...) → appendable?
v : appendable?
procedure
(..> v ...) → appendable?
v : appendable?
.., ∘, and ..> are deprecated and will be removed in a future version. Use ~ for concatenation, and if you need left-to-right composition for functions, consider using Threading Macros.
> (~ "hi" " " "there") "hi there"
> (~ '(1 2 3) '(4 5 6)) '(1 2 3 4 5 6)
> (~ (hash 'a 1 'b 2) (hash 'c 3)) '#hash((a . 1) (b . 2) (c . 3))
> ((~ ->string +) 3 4) "7"
procedure
(* v ...) → multipliable?
v : multipliable?
> (* 1 2 3 4) 24
procedure
(id operation) → procedure?
operation : procedure?
> ((id add) 3) 0
> ((id multiply) 3) 1
> ((id add) #(1 2 -3)) '#(0 0 0)
> ((id append) "hi") ""
> ((id append) '(1 2 3)) '()
> ((id ~) "hi") ""
> ((id +) 3) 0
> ((id *) 3) 1
procedure
(inverse operation) → procedure?
operation : procedure?
procedure
(/ v ...) → multipliable?
v : multipliable?
procedure
(fold f seqs [ #:into base #:order order #:direction direction #:with-steps? with-steps?]) → any/c f : procedure? seqs : (listof (sequenceof any/c)) base : any/c = undefined order : (one-of/c 'abb 'bab) = 'abb direction : (one-of/c 'left 'right) = 'right with-steps? : boolean? = #f
procedure
(foldl f seqs [ #:into base #:order order #:with-steps? with-steps?]) → any/c f : procedure? seqs : (listof (sequenceof any/c)) base : any/c = undefined order : (one-of/c 'abb 'bab) = 'abb with-steps? : boolean? = #f
procedure
(foldr f seqs [ #:into base #:order order #:with-steps? with-steps?]) → any/c f : procedure? seqs : (listof (sequenceof any/c)) base : any/c = undefined order : (one-of/c 'abb 'bab) = 'abb with-steps? : boolean? = #f
With folding operations there are two parameters that one may wish to tweak. The first is the direction of the fold, either left or right, for which one may use either foldl or foldr. The second is the order in which arguments are supplied to the folding function f, which may be controlled by the keyword argument #:order, with a value of 'abb corresponding to the accumulator always being passed last, consistent with Racket’s built-in foldl, and a value of 'bab corresponding to the accumulator always being passed first, consistent with the version of foldl found in data/collection and also in some other functional languages like Haskell.
In many common cases, modulating the folding direction and/or the argument order does not make a difference to the result. Specifically, in those cases where the operation is commutative and closed, it doesn’t matter whether you use foldl or foldr, or whether you use argument order 'abb or 'bab. The result would be the same. However, in cases where the operation is not closed, argument order becomes significant. As a general guideline, choose between foldl and foldr in cases where the operation is not commutative (a relatively common case, such as string concatenation), and between the two argument orders in cases where the operation isn’t closed (a less common case, such as type constructors).
Additionally, note that foldl computes values lazily, whereas foldr is not lazy.
foldl is equivalent to calling fold with #:direction 'left, and foldr is equivalent to calling fold with #:direction 'right. fold/steps is equivalent to calling fold with #:with-steps? #t.
> (fold + '(1 2 3 4)) 10
> (fold * '(1 2 3 4)) 24
> (fold ~ '("hi" " " "there")) "hi there"
> (foldr + '(1 2 3 4)) 10
> (foldl + '(1 2 3 4)) 10
> (foldr + '(1 2 3 4) #:order 'bab) 10
> (foldl + '(1 2 3 4) #:order 'bab) 10
> (foldr ~ '("hi" " " "there")) "hi there"
> (foldl ~ '("hi" " " "there")) "there hi"
> (foldr cons '(1 2 3) #:into '() #:order 'abb) '(1 2 3)
> (foldl cons '(1 2 3) #:into '() #:order 'abb) '(3 2 1)
> (foldr cons '(1 2 3) #:into '() #:order 'bab) '(((() . 3) . 2) . 1)
> (foldl cons '(1 2 3) #:into '() #:order 'bab) '(((() . 1) . 2) . 3)
procedure
(fold/steps f seqs [ #:into base #:order order #:direction direction]) → any/c f : (-> any/c any/c any/c) seqs : (listof (sequenceof any/c)) base : any/c = undefined order : (one-of/c 'abb 'bab) = 'abb direction : (one-of/c 'left 'right) = 'right
procedure
(foldl/steps f seqs [ #:into base #:order order]) → any/c f : (-> any/c any/c any/c) seqs : (listof (sequenceof any/c)) base : any/c = undefined order : (one-of/c 'abb 'bab) = 'abb
procedure
(foldr/steps f seqs [ #:into base #:order order]) → any/c f : (-> any/c any/c any/c) seqs : (listof (sequenceof any/c)) base : any/c = undefined order : (one-of/c 'abb 'bab) = 'abb
> (->list (fold/steps + '(1 2 3 4))) '(0 4 7 9 10)
> (->list (foldr/steps + '(1 2 3 4))) '(0 4 7 9 10)
> (->list (foldl/steps + '(1 2 3 4))) '(0 1 3 6 10)
> (->list (foldr/steps * '(1 2 3 4))) '(1 4 12 24 24)
> (->list (foldl/steps * '(1 2 3 4))) '(1 1 2 6 24)
> (->list (foldr/steps ~ '("hi" " " "there"))) '("" "there" " there" "hi there")
> (->list (foldl/steps ~ '("hi" " " "there"))) '("" "hi" " hi" "there hi")
procedure
seqr : sequencer? seed : any/c
procedure
(unfoldl seqr seed) → collection?
seqr : sequencer? seed : any/c
procedure
(unfoldr seqr seed) → collection?
seqr : sequencer? seed : any/c
All of these operations leverage the generic type constructor : by default, so that a constructor usually need not be provided in the sequencer specification, and the type of the resulting sequence would be inferred from the type of the tail (which defaults to a list).
unfold is essentially the same as unfoldl, except that it returns values lazily (i.e. produces a stream). unfoldl and unfoldr are not lazy.
> (define naturals (unfold (sequencer values add1) 0)) > (->list (take 10 naturals)) '(0 1 2 3 4 5 6 7 8 9)
> (unfoldl (sequencer sqr add1 #:stop? (λ (x) (> x 10))) 1) '(1 4 9 16 25 36 49 64 81 100)
> (unfoldr (sequencer sqr sub1 #:stop? zero?) 10) '(1 4 9 16 25 36 49 64 81 100)
> (unfoldl (sequencer car cdr #:stop? null?) '(h e l l o)) '(h e l l o)
> (unfoldr (sequencer car cdr #:stop? null?) '(h e l l o)) '(o l l e h)
> (define fibs (unfold (sequencer sum (match-lambda [(list a b) (list b (+ a b))])) (list 0 1))) > (->list (take 10 fibs)) '(1 2 3 5 8 13 21 34 55 89)
> (define symbol+1 (..> ->char ->number add1 ->char ->symbol))
> (unfoldl (sequencer values (λ (x) (cons (symbol+1 (car x)) (add1 (cdr x)))) #:stop? (λ (x) (> (cdr x) 10)) #:tail (thunk* (hash))) '(a . 1))
'#hash((a . 1)
(b . 2)
(c . 3)
(d . 4)
(e . 5)
(f . 6)
(g . 7)
(h . 8)
(i . 9)
(j . 10))
procedure
fs : (sequenceof procedure?) v : any/c
> (->list (onto (list add1 sub1 ->string) 0)) '(1 -1 "0")
> (->list (onto (list + * min max) 7 6 9)) '(22 378 6 9)
> (define (conjoin . fs) (~ all? (curry onto fs))) > ((conjoin positive? even? integer?) 4) #t
> (define (n·xⁿ [n 0]) (stream-cons (~ (curry * n) (curryr expt n)) (n·xⁿ (add1 n)))) > (->list (take 10 (onto (n·xⁿ) 3))) '(0 3 18 81 324 1215 4374 15309 52488 177147)
> (->list (take 10 (onto (map ~ (repeat ->string) (n·xⁿ)) 3))) '("0" "3" "18" "81" "324" "1215" "4374" "15309" "52488" "177147")
procedure
(join vs) → appendable?
vs : (sequenceof appendable?)
> (join (list "hello" " " "there")) "hello there"
> (join (stream '(1 2 3) '(4 5 6))) '(1 2 3 4 5 6)
> (join (list number->string add1 sqr)) #<procedure:composed>
> (join (list 1 2 3 4)) 10
> (join (list #(1 2 3) #(1 2 3) #(1 2 3))) '#(1 2 3 1 2 3 1 2 3)
> (join (list (stream 1 2 3) (stream 1 2 3) (stream 1 2 3))) #<stream>
procedure
vs : (sequenceof addable?)
procedure
(product vs) → multipliable?
vs : (sequenceof multipliable?)
procedure
v : any/c n : integer? op : procedure? = ~
procedure
n : integer? op : procedure? = *
Whenever a function produces an output of the same type as its input (i.e. in mathematical terms it is a self-map), it has a well-defined notion of "powers." For example, cdr is a self-map on lists, but car is not.