/
morphism.d
147 lines (114 loc) · 4.64 KB
/
morphism.d
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// Written in the D programming language
/**
To Be Documented.
An attempts to code generalization of folding/unfolding algorithms on branching structures, also
known under the delightful names of catamorphisms, anamorphisms, paramorphisms and hylomorphisms.
License: <a href="http://www.boost.org/LICENSE_1_0.txt">Boost License 1.0</a>.
Authors: Philippe Sigaud
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
*/
module dranges.morphism;
import std.algorithm,
std.array,
std.functional,
std.range,
std.traits,
core.vararg;
import dranges.algorithm,
dranges.functional,
dranges.templates,
dranges.traits,
dranges.tuple,
dranges.typetuple;
/**
Catamorphism.
The equivalent of reduce, on recursive ranges: it collapses an entire recursive range into one value. Or,
if you will and if the propagated value is complex, recursively builds a value from a tree.
$(M fun) takes as arguments the front value of the recursive range and the range of results coming from
applying the catamorphism on the successors. That is, one step in the building is that you already
applied $(M fun) to the successors. From this range of temporary results and the current node's value,
you build the current result, which you return 'upward', to the preceding level of recursion.
So, if the node is a sink/leaf (no successors or the only successor is empty), the range of result is also empty.
This version take a standard function. It's the equivalent of reduce(range).
*/
ReturnType!fun cata(alias fun, T)(T tr)
{
auto ch = array(map!(cata!(fun,T))(tr.successors)); // You have to get rid of array to have an infinite list of successors
return fun(ch,tr.value);
}
int h(int[] heights, ...)
{
return 1 + maxOf(0 ~ heights);
}
T m(T)(T[] maxs, T value) { return maxOf(maxs ~ value);}
T[] preord(T)(T[][] pos, T value) { return value ~ array(range2.flatten(pos));}
T[] postord(T)(T[][] pos, T value) { return array(range2.flatten(pos)) ~ value;}
NTree!T cons(T)(NTree!T[] trees, T value) { return ntree(value, trees);}
NTree!(Tuple!(T,int)) withDepth(T)(NTree!(Tuple!(T,int))[] trees, T value)
{
int d = 1 + maxOf(0 ~ array(map!"a.value.field[1]"(trees))); // find current depth
return ntree(tuple(value, d), trees);
}
int numNodes(int[] numnodes, ...) { return sum(1 ~ numnodes);}
/**
Anamorphism.
The equivalent of unfold for recursive ranges: creates a entire tree from
a generative function $(M gen), a seed value, and a predicate (on the current value) as the stopping condition.
*/
class Ana(alias gen, alias pred, T) {
T value;
this(T t) { value = t;}
Ana!(gen,pred,T)[] successors() {
return unaryFun!pred(value) ? (typeof(return)).init : array(map!(ana!(gen,pred,T))(unaryFun!gen(value)));
}
}
///
Ana!(gen,pred,T) ana(alias gen, alias pred, T)(T t) {
return new Ana!(gen,pred,T)(t);
}
/**
Paramorphism
The equivalent of reduce, but with a ternary function constructor(front of the range, tail of the range, paramorphism on the tail)
*/
typeof(ifEmpty) para(alias ifEmpty, alias constructor, R)(R range) if (isInputRange!R)
{
if (range.empty) return ifEmpty;
auto f = range.front;
range.popFront;
return naryFun!constructor(f, range, para!(ifEmpty, constructor)(range));
}
/**
Hylomorphism, the composition of a catamorphism (which collapse a recursive range) with an anamorphism (which builds a recursive range).
Examples?
*/
typeof(ifTrue) hylo(alias ifTrue, alias constructor, alias predicate, alias next, T)(T t)
{
if (unaryFun!predicate(t)) return ifTrue;
auto state = unaryFun!next(t); // (b, a')
return binaryFun!constructor(first(state), hylo!(ifTrue, constructor, predicate, next)(second(state)));
}
unittest
{
int[] nums = [1,2,3,4,5];
int[] e;
auto t = para!(e, "(a ~ b) ~ c")(nums);
// wr(t);
auto fact = para!(1, "(a+1)*c")([5,4,3,2,1]);
// writeln(fact);
auto fact2 = hylo!(1, "a*b", "a==0", "tuple(a, a-1)")(5);
// writeln(fact2);
int[][] h;
auto heads =reduce!"a~(a[$-1]~b)"(h ~ e,nums);
// wr(heads);
bool pred(int i) { return i > 3_000_000;}
int[] gen(int i) { return [i+1,i*2];}
int[] collatz(int i) { return ((i-4)%6 == 0 && (i > 4)) ? [i*2,(i-1)/3] : [i*2];}
auto n5 = ana!(collatz, "a>=1_00")(1);
// writeln(cata!numNodes(n5), " numbers found.");
// writeln("Longest sequence contains ", cata!h(n5), " nodes.");
// writeln(cata!(toS!int)(n5));
/* todo: isRecursiveContainer. do not ask for a NTree when you don't need one*/
// wr(map!"a.value"(traversal(n5)));
// writeln(cata!(preord!int)(n5));
}