git.iko.soy/urbit.org
on f3ca521 help sign in
urbit.org/tutorials/hoon-tutorial/fibonacci.md
63 lines 2.5 kB history raw
1+++
2title = "1.4.1 Walkthrough: Fibonacci Sequence"
3weight = 7
4template = "doc.html"
5aliases = ["/docs/learn/hoon/hoon-tutorial/fibonacci/"]
6+++
8In this example, we will write a generator that produces a list of Fibonacci numbers up to `n`.
10```hoon
11|= n=@ud
12%- flop
13=+ [i=0 p=0 q=1 r=*(list @ud)]
14|- ^+ r
15?: =(i n) r
16%= $
17 i +(i)
18 p q
19 q (add p q)
20 r [q r]
21==
22```
24On the first line, we use `|=` to produce a gate which takes an `@ud` that's stored in the face `n`. This `n` sample that we give our gate determines how long our Fibonacci sequence is. When the list that our program builds has `n` members, the program ends.
26```hoon
27%- flop
28```
30In the line above, we use `flop` on the output of the rest of the program. `flop` is a standard library function to reverse a list.
32Why are we using this instead of just producing the list in the order we want it in the first place? Because with lists, adding an element to the end is a computationally expensive operation that gets more expensive the longer the list is, due to the fact that you need to traverse to the end of the tree. Adding an element to the front, however, is cheap. [In Big-O Notation](https://en.wikipedia.org/wiki/Big_O_notation), adding to the end of a list is O(n) and the front is O(1).
34```hoon
35=+ [i=0 p=0 q=1 r=*(list @ud)]
36```
38Here we declare several values that we are going to use the execution of our program. The only one of these that is noteworthy is `r`: we're using `*` to bunt, or get the default value for, the mold `(list @ud)`.
40```hoon
41|- ^+ r
42```
44With this code, we define `|-`, the _trap_ that acts as a recursion point and contains the rest of our program. We also use `^+` to cast the output by example. This will result in the output being the same type as `r`, a list of `@ud`.
46```hoon
47?: =(i n) r
48```
50In the code above, `?:` checks whether the first child, `=(i n)`, our terminating case, is true or false. If it is true, it branches to `r` and the program ends. If it is false, the program continues to the code below.
52```hoon
53%= $
54 i +(i)
55 p q
56 q (add p q)
57 r [q r]
58==
59```
61The final expression in our program calls the `$` arm of the trap we are but makes some changes: we increment `i`, set `p` to be `q` and `q` becomes the sum of `p` and `q`. `r` becomes a cell of `q` and whatever `r` was previously. The list built from this is the one that will get `flop`ped to produce the result at the end of the computation.
63### [Next Up: Reading -- Gates](../gates)