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
|
# Recursion and Functional Composition
This guide shows how to express recursion (including mutual recursion) and how to build programs by composing small functions...probably read the [documentation about functional programming](./01_functional.md) before this.
## Simple Recursion
```baba
// Factorial
factorial : n ->
when n is
0 then 1
1 then 1
_ then n * (factorial (n - 1));
// Fibonacci
fibonacci : n ->
when n is
0 then 0
1 then 1
_ then (fibonacci (n - 1)) + (fibonacci (n - 2));
```
## Tail-Recursion with an Accumulator
```baba
// Sum of digits using an accumulator
sumDigits : n acc ->
when n is
0 then acc
_ then sumDigits (n / 10) (acc + (n % 10));
sumDigitsStart : n -> sumDigits n 0;
```
## Mutual Recursion
```baba
// Using with rec in a header to define mutually recursive locals
isEvenOdd : z -> with rec (
isEven : n ->
when n is
0 then true
_ then isOdd (n - 1);
isOdd : n ->
when n is
0 then false
_ then isEven (n - 1);
) -> { even: isEven 10, odd: isOdd 7 };
```
## Function Composition
Baba Yaga provides built-in function combinators for composition. For detailed documentation, see [Functional Programming](./01_functional.md#function-combinators).
```baba
inc : x -> x + 1;
double : x -> x * 2;
// Built-in compose (right-to-left): f(g(x))
composed : compose inc double;
r1 : composed 3; // inc (double 3) = 7
// Built-in pipe (left-to-right): value |> function
r2 : pipe 3 inc; // inc 3 = 4
r3 : pipe 4 double; // double 4 = 8
```
## Composing Many Functions
You can compose an arbitrary list of unary functions using `reduce`.
```baba
// composeAll [f, g, h] = x -> f (g (h x))
composeAll : funcs ->
reduce (acc fn -> (x -> acc (fn x))) (x -> x) funcs;
inc : x -> x + 1;
double : x -> x * 2;
combo : composeAll [inc, double];
res : combo 3; // inc (double 3) = 7
```
## Recursion with Utility Functions
Using the enhanced utility functions for recursive algorithms:
```baba
// Recursive data processing with validation
processNumbers : numbers ->
when (validate.notEmpty numbers) is
false then []
true then
with (
sorted : sort.by numbers (x -> x);
chunks : chunk sorted 3;
processed : map (chunk -> reduce (acc x -> acc + x) 0 chunk) chunks;
) ->
processed;
// Recursive tree traversal with debugging
traverseTree : tree ->
with rec (
// Debug each node we visit
visitNode : node ->
when (validate.notEmpty (keys node)) is
false then (debug.print "Empty node"; 0)
true then
with (value : node.value;) ->
(debug.print "Visiting" value; value);
// Recursive traversal
traverse : node ->
when (validate.notEmpty (keys node)) is
false then 0
true then
(visitNode node) +
(traverse node.left) +
(traverse node.right);
) ->
traverse tree;
// Generate and process sequences recursively
fibonacci : n ->
when (validate.range 0 100 n) is
false then (assert false "n must be 0-100"; 0)
true then
when n is
0 then 0
1 then 1
_ then (fibonacci (n - 1)) + (fibonacci (n - 2));
// Generate fibonacci sequence using range and recursion
fibSequence : count ->
with (indices : range 0 (count - 1);) ->
map fibonacci indices;
// Example: fibSequence 10 generates [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
```
|