2.3 Traversals

8.16.0.4

2.3 Traversals🔗ℹ

(require ocular-patdown/optics/traversal)
	package: ocular-patdown

A traversal is an optic that can have zero or more foci. Updating with a traversal is like using map.

Examples:

> (traversal-map list-traversal (list 1 2 3) add1)
'(2 3 4)
> (traversal-foldl list-traversal (list 1 2 3) cons '())
'(3 2 1)

All lenses are traversals, but not all traversals are lenses.

procedure
(traversal? val) → boolean?
val : any/c

Predicate for traversals. Recognizes implementers of gen:traversal.

Examples:

> (traversal? list-traversal)
#t
> (traversal? car-lens)
#t

procedure
(make-traversal map-proc fold-proc) → traversal?
map-proc : (-> (-> any/c any/c) any/c any/c)
fold-proc : (-> (-> any/c any/c any/c) any/c any/c any/c)

Constructor for traversals. Takes in a function like map and a function like foldl, but the functions should operate on the foci within the target.

Examples:

> (define my-list-traversal (make-traversal map foldl))
> (define my-maybe-traversal
    (make-traversal
      (lambda (proc val) (if val (proc val) val))
      (lambda (proc init val) (if val (proc val init) init))))

There are a few laws traversals should obey:

traversal-maping a target under a traversal should leave it with the same number of foci.
traversal-foldl should not call the folding procedure with the same focus twice.

Like lenses, traversals should be pure.

2.3.1 Traversal Operations🔗ℹ

procedure
(traversal-map traversal target proc) → any/c
  traversal : traversal?
  target : any/c
  proc : (-> any/c any/c)

Apply proc to each focus of target under traversal. Like map.

Examples:

> (traversal-map list-traversal (list 1 2 3) add1)
'(2 3 4)
> (traversal-map vector-traversal (vector 1 2 3) sub1)
'#(0 1 2)

procedure
(traversal-foldl traversal target proc init) → any/c
  traversal : traversal?
  target : any/c
  proc : (-> any/c any/c any/c)
  init : any/c

foldl over the foci of target under traversal.

Examples:

> (traversal-foldl list-traversal (list 1 2 3) + 0)
6
> (traversal-foldl vector-traversal (vector 1 2 3) cons '())
'(3 2 1)

procedure
(traversal->list traversal target) → (listof any/c)
traversal : traversal?
target : any/c

Get a list of all foci of target under traversal.

Example:

> (traversal->list vector-traversal (vector 1 2 3 4))
'(1 2 3 4)

procedure
(traversal-compose traversal ...) → traversal?
traversal : traversal?

Compose traversals like optic-compose.

Examples:

> (define lol-traversal (traversal-compose list-traversal list-traversal))
> (traversal-map lol-traversal '((1 2 3) () (4)) add1)
'((2 3 4) () (5))
> (traversal-map (traversal-compose list-traversal maybe-traversal car-lens)
'(#f (10 20 30) #f (40 50))
sqr)
'(#f (100 20 30) #f (1600 50))

2.3.2 Library Traversals🔗ℹ

value
list-traversal : traversal?

Traversal that focuses on each element of a list.

Examples:

> (traversal-map list-traversal (list 1 2 3) add1)
'(2 3 4)
> (traversal-foldl list-traversal (list 1 2 3) cons '())
'(3 2 1)

value
vector-traversal : traversal?

Traversal that focuses on each element of a vector.

Examples:

> (traversal-map vector-traversal (vector 1 2 3) add1)
'#(2 3 4)
> (traversal-foldl vector-traversal (vector 1 2 3) cons '())
'(3 2 1)

value
rose-traversal : traversal?

Traversal that focuses on each leaf of a rose tree, where a rose tree is either a non-list or a list of rose trees.

Raises an exception when mapping results in a focus turning into a list since this could lead to the number of foci changing.

Examples:

> (traversal-map rose-traversal '((1 2) () ((3) 4)) add1)
'((2 3) () ((4) 5))
> (traversal-foldl rose-traversal '(("a" "b") "c") string-append "")
"cba"

value
maybe-traversal : traversal?

Traversal that focuses on the target if it is not #f, and has no focus otherwise. Useful to compose with other optics to get optional behavior.

Examples:

> (traversal-map maybe-traversal 1 add1)
2
> (traversal-map maybe-traversal #f add1)
#f
> (traversal->list maybe-traversal 1)
'(1)
> (traversal->list maybe-traversal #f)
'()
> (traversal-map (traversal-compose list-traversal maybe-traversal car-lens)
'(#f (10 20 30) #f (40 50))
sqr)
'(#f (100 20 30) #f (1600 50))

2.3.3 Traversal Combinators🔗ℹ

procedure
(traversal-append trv ...) → traversal?
trv : traversal?

A traversal that focuses on the foci of each traversal. Useful when you have multiple traversals with the same target but different foci and want to combine them.

Example:

> (traversal-map (traversal-append car-lens cdr-lens) (cons 1 2) add1)
'(2 . 3)

Note: In order for this to be a lawful traversal, the foci of the input traversals must never have overlap.

syntax
(if-traversal pred then-traversal else-traversal)

A conditional traversal that has the behavior of either then-traversal or else-traversal depending on the result of applying the predicate to the target. Useful for creating recursive traversals.

Wraps then-traversal and else-traversal with lazy-traversal.

Examples:

> (struct bt [left right] #:transparent)
> (struct leaf [value] #:transparent)
> (define bt-values-traversal
    (if-traversal bt?
                  (traversal-compose (traversal-append (struct-lens bt left) (struct-lens bt right))
                                     bt-values-traversal)
                  (struct-lens leaf value)))
> (define bt1 (bt (leaf 1)
                  (bt (bt (leaf 2)
                          (bt (leaf 3)
                              (leaf 4)))
                      (leaf 5))))
> (traversal->list bt-values-traversal bt1)
'(1 2 3 4 5)
> (traversal-map bt-values-traversal bt1 add1)
(bt (leaf 2) (bt (bt (leaf 3) (bt (leaf 4) (leaf 5))) (leaf 6)))

In order for such a traversal to be lawful, it is a good idea to make sure it’s impossible for traversal-map to change the result on the condition of the target. In other words, if a target will end up using then-traversal, mapping over its foci better not cause the resulting target to use the else-traversal or vice versa. That’s why rose-traversal has the restriction that the mapped procedure cannot return a list.

syntax
(lazy-traversal body ...)

A lazy traversal that evaluates body ... at most once. Useful for creating recursive traversals.

Examples:

> (struct tree [value children] #:transparent)
> (define tree1 (tree 1 (list (tree 2 (list (tree 3 '())))
                              (tree 4 '()))))
> (define tree-value-lens (struct-lens tree value))
> (define tree-children-lens (struct-lens tree children))
> (define tree-children-traversal (traversal-compose tree-children-lens list-traversal))
> (define tree-values-traversal
    (lazy-traversal (traversal-append tree-value-lens
                                      (traversal-compose tree-children-traversal tree-values-traversal))))
> (traversal-foldl tree-values-traversal tree1 + 0)
10

2.3.4 Generic Traversal Interface🔗ℹ

syntax
gen:traversal

A generic interface for traversals.

Example:

> (struct make-traversal (map foldl)
    #:methods gen:traversal
    [(define (traversal-map t target proc)
       ((make-traversal-map t) proc target))
     (define (traversal-foldl t target proc init)
       ((make-traversal-foldl t) proc init target))])

2.1	Optics
2.2	Lenses
2.3	Traversals
2.4	Isomorphisms
2.5	Prisms
2.6	Pattern-based Updating

2.3.1	Traversal Operations
2.3.2	Library Traversals
2.3.3	Traversal Combinators
2.3.4	Generic Traversal Interface