blob: 451fc61436226eb2c39fda352a144343d8f98f6f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
(.module:
[library
[lux #*
[abstract
[functor (#+ Functor)]
[equivalence (#+ Equivalence)]
[fold (#+ Fold)]
[monad (#+ do)]]
[control
["<>" parser
["<.>" code (#+ Parser)]]]
[data
[collection
["." list ("#\." monad fold)]]]
[macro
[syntax (#+ syntax:)]
["." code]]]])
(type: .public (Tree a)
{#.doc (example "A generic tree data-structure.")}
{#value a
#children (List (Tree a))})
(def: .public (flat tree)
{#.doc (example "All the leaf values of the tree, in order.")}
(All [a] (-> (Tree a) (List a)))
(|> tree
(get@ #children)
(list\map flat)
list\join
(#.Item (get@ #value tree))))
(def: .public (leaf value)
(All [a] (-> a (Tree a)))
{#value value
#children (list)})
(def: .public (branch value children)
(All [a] (-> a (List (Tree a)) (Tree a)))
{#value value
#children children})
(type: #rec Tree_Code
[Code (List Tree_Code)])
(def: tree^
(Parser Tree_Code)
(|> (|>> <>.some
<code>.record
(<>.and <code>.any))
<>.rec
<>.some
<code>.record
(<>.else (list))
(<>.and <code>.any)))
(syntax: .public (tree [root tree^])
{#.doc (example "Tree literals."
(: (Tree Nat)
(tree 12
{34 {}
56 {}
78 {90 {}}})))}
(in (list (` (~ (loop [[value children] root]
(` {#value (~ value)
#children (list (~+ (list\map recur children)))})))))))
(implementation: .public (equivalence super)
(All [a] (-> (Equivalence a) (Equivalence (Tree a))))
(def: (= tx ty)
(and (\ super = (get@ #value tx) (get@ #value ty))
(\ (list.equivalence (equivalence super)) = (get@ #children tx) (get@ #children ty)))))
(implementation: .public functor
(Functor Tree)
(def: (map f fa)
{#value (f (get@ #value fa))
#children (list\map (map f)
(get@ #children fa))}))
(implementation: .public fold
(Fold Tree)
(def: (fold f init tree)
(list\fold (function (_ tree' init') (fold f init' tree'))
(f (get@ #value tree)
init)
(get@ #children tree))))
|
