2017-09-29

(sph tree)

processing tree-like list structures.

library description

denoted

  a representation using pairs where the first element denotes the nesting level and the second element is content

  (a b (c (d e)) f)-> ((0 . a) (1 . b) (2 . c) (3 . d) (3 . e) (0 . 4))

prefix-tree

  first elements of lists interpreted as parent of tail elements. similar to scheme code for procedure application

  (a b (c (d e)) f)

  example with nesting marked by indent

    a

      b

      c

        d

          e

      f

import name

(sph tree)

exports

denoted-tree->prefix-tree

procedure

signature

a [depth-start] ->

list [integer] -> list

description

convert a tree representation like this ((0 a) (1 b) (2 c) (1 d)) to this (a (b c) d).

cases like ((0 a) (3 b) (0 c)) are converted to (a ((b)) c)

denoted-tree->tree

procedure

signature

a [depth-start] ->

list:((integer any ...) ...) [integer] -> list

description

convert a tree representation like this ((0 a) (1 b) (2 c) (1 d)) to this (a (b (c) d))

denoted-tree->tree-inner

syntax

signature

a depth-start r-2 r update-r ...

denoted-tree-adjust-depth

procedure

signature

a operator arguments ... ->

procedure list integer -> list

description

map the nesting-depth of each element with operator and arguments.

the lowest possible depth is bounded to zero.

example:

(denoted-tree-adjust-depth a + 1)

denoted-tree-minimise-depth

procedure

signature

a ->

procedure list integer -> list

description

decrease nesting-depth for all element until at least one element has a nesting-depth of zero

prefix-tree->denoted-tree

procedure

signature

a initial-depth ... ->

list [integer] -> list

like tree ->

description

denoted-tree but the nesting-depth number corresponds to prefix-tree interpretation. example

(a b (c (d e)) f) -> ((0 . a) (1 . b) (2 . c) (3 . d) (3 . e) (0 . 4))

prefix-tree->infix-tree

procedure

signature

a [prefix->infix] ->

list [procedure:{any -> any}] -> list

description

converts list structures like (or a b (and c d)) to (a or b or (c and d))

the optional procedure translates prefixes

prefix-tree->paths

procedure

signature

a ->

list -> (string ...)

description

regard tree as a nested list representation of a filesystem file and directory structure

and return a flat list of filesystem path strings.

example:

(prefix-tree->paths (list "/usr" (list "bin" (list "share" "guile") "include") "/var"))

creates

(list

"/usr/bin"

"/usr/share/guile"

"/usr/include"

"/var")

prefix-tree->relations

procedure

signature

a ->

list -> (pair ...)

description

create a list of all individual relations between prefix and tail elements or tail element prefixes.

example:

((a (b c (d e)))) -> ((a . b) (b . c) (b . d) (d . e))

prefix-tree-context-match

procedure

signature

a pattern ->

list list -> boolean

description

true if pattern exists in prefix-tree with the same tree interpretation as prefix-tree-context-produce.

example: (a b (d c)) contains patterns (a d c) and (a b) and (a d)

prefix-tree-map

procedure

signature

f a ->

description

{any:prefix list:tail} list -> list

map only lists, split into prefix and tail

prefix-tree-map-c

procedure

signature

f continue& a ->

description

procedure:{prefix tail} procedure:{list procedure:f procedure:continue:{list ->}} list -> list

maps over only the lists, split into prefix and tail.

the procedure continue& gets a procedure argument that when called continues the iteration. if it is not called,

the iteration stops and the result of continue& is the main result

prefix-tree-map-c-depth

procedure

signature

f continue a [inc depth-init] ->

description

{any:prefix list:tail any} {list procedure:f {list ->} any}:continue list [{integer -> integer}] -> list

like prefix-tree-map-c but with additional arguments for the current nesting-depth

prefix-tree-map-depth

procedure

signature

f a [initial-depth] ->

{any:prefix list:tail integer:depth -> any} list [integer] -> list

description

like prefix-tree-map but with an additional argument for the current nesting-depth

prefix-tree-map-depth-flat

procedure

signature

proc a initial-depth ... ->

{integer any -> any} list [integer] -> (any ...)

like tree ->

description

denoted-tree-->flat but the nesting-depth number corresponds to prefix-tree interpretation

prefix-tree-map-with-context

procedure

signature

f a ->

description

{any list:upper-prefixes} list -> list

like (prefix-tree-map) but with an additional argument for parent prefixes

prefix-tree-produce

procedure

signature

f a ->

{any ... -> any} list:prefix-tree -> list

description

calls f for each combination of prefix and tail

prefix-tree-produce-with-context

procedure

signature

f a [ignore-prefixes] ->

{element context -> any} list -> list

description

context is a list containing nested-list prefixes in bottom-to-top order.

for example (a (d e f) k (g h i) j) leads to f called with each of the following arguments:

(d (a)), (e (d a)), (f (d a)),(k (a)), (g (a)), (h (g a)), (i (g a)), (j (a))

ignore-prefixes ignores lists that are themselves prefixes

prefix-tree-produce-with-context-mm

procedure

signature

f a ->

procedure:{any list -> any} list -> list

description

like prefix-tree-produce-with-context but creates many-to-many relations from lists as list prefixes

prefix-tree-product

procedure

signature

a [ignore-prefixes?] ->

prefix-tree-product-mm

procedure

signature

a ->

prefix-tree-replace-prefix

procedure

signature

a replacements ->

list ((to-replace . replacement) ...) -> list

description

replace all list prefixes, the first element of a list, in tree based on the given replacements structure

sph-tree-description

variable

tree->denoted-tree

procedure

signature

a initial-depth ... ->

list [integer] -> list

description

convert a tree to an association list where each element is a list having a nesting-depth number

as the first element. similar to this is the usage of indentation for nesting depth.

(a b (c (d e)) f) -> ((0 . a) (0 . b) (1 . c) (2 . d) (2 . e) (0 . f))

tree-any

procedure

signature

f a ->

procedure list -> false/any

description

call f with each tree element list or leaf from top to bottom and return the first true result of f.

can be used to extract single elements from tree. aliased as tree-any and tree-extract

tree-contains-all?

procedure

signature

a equal? search-values ... ->

list {any any -> boolean} any ... -> boolean

description

like tree-contains? but true only if every of the search-values has been found

tree-contains-some-not?

procedure

signature

a equal? search-values ... ->

list {any any -> boolean} any ... -> boolean

description

like tree-contains? but true only if any of the search-values is not contained

tree-contains-some?

procedure

signature

a equal? search-values ... ->

list {any any -> boolean} any ... -> boolean

description

like tree-contains? and true if any of the search-values is found

tree-contains?

procedure

signature

a search-value [equal?] ->

list any [procedure:{any any -> boolean}] -> boolean

description

compares all list and non-list elements with search-value and returns true on a match

tree-each

procedure

signature

f a ->

procedure:{any ->} list ->

description

call f for every element in tree, lists and non-lists.

list elements left to right, nested lists bottom to top.

tree-for-each

tree-each-leaf

procedure

signature

f a ->

procedure:{any ->} list ->

description

call f for each non-list element in tree

tree-every

procedure

signature

f a ->

tree-extract

procedure

signature

f a ->

procedure list -> false/any

description

call f with each tree element list or leaf from top to bottom and return the first true result of f.

can be used to extract single elements from tree. aliased as tree-any and tree-extract

tree-filter

procedure

signature

predicate a ->

procedure:{element -> any/boolean} list -> list

description

call predicate for each non-list and list element in tree and

only keep the elements for which predicate returned true.

elements left to right, nested lists bottom to top.

example

(tree-filter (l (a) (or (list? a) (even? a))) (q (1 2 3 (4 5 (6 7) (8 9 10)))))

->

(2 (4 (6) (8 10)))

tree-filter-flat

procedure

signature

predicate a ->

procedure:{any -> boolean/any} list -> list

description

results in a flat list of all list and non-lists elements of tree

for which predicate returned true

tree-filter-leafs

procedure

signature

predicate a ->

description

like tree-filter but calls predicate only for non-list elements

tree-filter-lists

procedure

signature

predicate a ->

description

like tree-filter but calls predicate only for list elements.

example - keep only lists with more than 3 elements

(tree-filter-lists (l (a) (< 3 (length a))) (q (1 2 3 (4 5 (6 7) (8 9 10)))))

->

(1 2 3)

tree-find

procedure

signature

predicate a ->

procedure:{element -> any/boolean} list -> any

description

find a sub-tree that contains an element that matches predicate

tree-finder

procedure

signature

find f a ->

procedure:{predicate list ... -> any} procedure:{element -> any/boolean} list -> any

description

call f with each tree list and leaf from top to bottom and return true results of f

tree-fold

procedure

signature

p r t ->

procedure:{any:element any:result -> any:result} any:result list:tree -> any

description

fold over all lists and non-list elements in tree

elements from left to right, nested lists bottom to top.

lists passed to f will be fold results from list elements that have already been processed.

see tree-fold-right for examples

tree-fold-depth

procedure

signature

p r t [n inc] ->

description

procedure:{element result integer:depth} any tree [integer:depth procedure:{integer -> integer}] -> any

like tree-fold but keeps track of the current nesting depth

tree-fold-right

procedure

signature

p r t ->

procedure:{any:element any:result -> any:result} any:result list:tree -> any:result

description

fold over all list and non-list elements in tree.

elements from left to right, nested lists bottom to top

example 1

(tree-fold-right

(l (a r) (pair a r))

(list)

(q (1 2 3 (4 5 (6 7) (8 9 10)))))

->

(q (1 2 3 (4 5 (6 7) (8 9 10))))

example 2

(tree-fold-right

(l (a r) (if (list? a) a (if (even? a) (pair a r) r)))

(list) (q (1 2 3 (4 5 (6 7) (8 9 10)))))

->

(q (1 2 3 (4 5 (6 7) (8 9 10))))

tree-fold-right-depth

procedure

signature

f r t [depth inc] ->

procedure:{any:element any:result -> any:result} any:result list:tree -> any

description

fold over all list and non-list elements in tree.

elements from left to right, nested lists bottom to top

tree-map

procedure

signature

f a ->

procedure:{any -> any} list -> list

description

maps elements left to right and nested lists bottom to top.

not map the topmost tree structure itself.

tree-map-depth

procedure

signature

f a [initial-depth] ->

description

procedure:{any:element integer:depth} list [integer] -> list

like tree-map but also passes a number for the current nesting depth to f

tree-map-depth-flat

procedure

signature

f a initial-depth ... ->

procedure:{integer:depth any:element -> any:result-element} list [integer] -> (any ...)

description

map elements of tree to a flat list. apply f with a number

stating how deeply the element is nested in other lists and the current element

tree-map-leafs

procedure

signature

f a ->

procedure:{any -> any} list -> list

description

call f only with non-list elements, all other elements are kept

tree-map-lists

procedure

signature

f a ->

{list -> any} list -> list

description

like tree-map but pass only the lists in tree to f, skipping and keeping non-list elements. bottom-to-top

tree-map-lists-depth

procedure

signature

f a [depth-init map-depth] ->

{list integer:depth -> any} list [integer {integer -> integer:next-depth}] -> list

description

like tree-map-lists with additional arguments for the current nesting depth

tree-map-lists-self

procedure

signature

f a ->

{list -> any} list -> list

description

like tree-map-and-self but calls f only for list elements

tree-map-self

procedure

signature

f a ->

{any -> any} list -> list

description

like tree-map-lists but also map the given list itself

tree-map-with-state

procedure

signature

f a init ... ->

{any any:custom-state-value ... -> list:custom-state-values} -> (list:mapped-elements any:custom-state-value ...)

description

like tree-map but can carry and update a number of custom values per call, similar to fold-multiple

tree-mapper

procedure

signature

map f a ->

procedure:{procedure list ... -> list} procedure:{element -> new-element} list -> list

description

map over lists and sub-lists using the given map procedure, which needs to have the same

signature as "map".

maps from bottom to top

tree-mapper-produce

procedure

signature

map f a b ->

procedure:{f list:elements -> any} procedure:{any:element-a any:element-b -> any}:f list list -> any

description

call f with each ordered combination between elements of two lists with a

map procedure that is called nested like

(each (lambda (a) (each (lambda (b) (f a b)) b)) a)

tree-mapper-top

procedure

signature

map f a ->

procedure:{procedure list ... -> list} procedure:{element -> new-element} list -> list

description

maps from top to bottom.

list results of f will be entered for further mapping.

this procedure is used to map sub-lists before eventually

mapping their elements if the map result is a list

tree-produce

procedure

signature

f a b ->

procedure:{any any -> any} list list -> any

description

apply f with every possible ordered combination of list and non-list elements of trees.

traverses like tree-map

tree-produce-lists

procedure

signature

f a b ->

description

like tree-produce only for list elements

tree-produce-lists-depth

procedure

signature

f a b [inc depth-init] ->

description

{any:element-a any:element-b integer:depth-a integer:depth-b} list:list-a list:list-b [{integer -> integer} integer] -> list

tree-replace-at-once

procedure

signature

predicate f a ->

procedure:{element -> boolean} procedure:{list:matched-elements -> list} list -> list

description

searches through tree recursively, collecting all elements (including lists) that match collect-proc, then calls

f with a list of matched elements. the result of f must of length zero (no replacement) or matched-element-count (replaces all matches).

results in the tree with the matched elements are replaced in order by the result elements from calling f

tree-replace-by-list

procedure

signature

a replace? replacements ->

list {any -> boolean} (any ...) -> list

description

replace each non-list element in tree that matches replace? with the next element from replacements.

it is an error if there are more replacements than matches

tree-splice

procedure

signature

predicate a ->

prodecure:{element -> boolean/any} list -> list

description

merge nested lists with that match predicate with their parent list.

example

(tree-splice (l (a) (= 3 (length a))) (q (1 2 3 (4 5 (6 7) (8 9 10)))))

->

(1 2 3 (4 5 (6 7) 8 9 10))

tree-transform

procedure

signature

a descend ascend terminal ->

list procedure procedure procedure -> any

description

descend :: any:element procedure:recurse-descend -> (any:result-element boolean:continue?)

ascend :: any:element -> any:result-element

terminal :: any:element -> any:result-element

map/transform list and sub-lists first top to bottom, calling "descend" for each sub-list,

then bottom to top, calling "ascend" for lists and "terminal" for non-lists/leafs.

descend should return a list of two values: the first for the result and the second a boolean indicating if the result

should be passed to ascend and terminal (true) or if that should be skipped (false).

example use cases:

* compile s-expression list trees into string output languages by mapping all expressions and sub-expressions to strings

* replace some lists in a tree

tree-transform*

procedure

signature

a descend ascend terminal states ... ->

list procedure procedure procedure any ... -> any

description

descend :: any:element procedure:recurse-descend any:state ... -> (any:result-element boolean:continue? any:state ...)

ascend :: any:element any:state ... -> (any:result-element any:state ...)

terminal :: any:element any:state ... -> (any:result-element any:state ...)

like tree-transform but also takes, passes and updates caller specified values

tree-transform-ascend

procedure

signature

rest leaf-list recurse-descend ascend terminal states ->

tree-transform-descend-identity

procedure

signature

a ... ->

any ... -> (#f #t)

description

a tree-transform descend procedure that does not do anything


tags: programming guile documentation library scheme sph-lib sph-tree