blob: 5b5c91271b0ea6d333953777b863c076bff973c7 (
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
|
(.module:
[lux #*
["_" test (#+ Test)]
[abstract/monad (#+ do)]
["%" data/text/format (#+ format)]
[control
["." io (#+ IO)]
["." state ("#@." monad)]]
[math
["r" random]]
[data
[number
["n" nat]]]
[time
["." instant]
["." duration (#+ Duration)]]]
{1
["." /
["/#" // #_
["#" mixin]]]})
(def: (fibonacci fibonacci input)
(/.Memo Nat Nat)
(case input
0 (state@wrap 0)
1 (state@wrap 1)
_ (do state.monad
[output-1 (fibonacci (n.- 1 input))
output-2 (fibonacci (n.- 2 input))]
(wrap (n.+ output-1 output-2)))))
(def: (time function input)
(All [i o] (-> (-> i o) i (IO [Duration o])))
(do io.monad
[before instant.now
#let [output (function input)]
after instant.now]
(wrap [(instant.span before after)
output])))
(def: #export test
Test
(<| (_.context (%.name (name-of /.memoization)))
(let [fast (/.closed n.hash fibonacci)
slow (/.none n.hash ..fibonacci)]
(do r.monad
[input (wrap 30)
#let [prefix (format (%.name (name-of /.memoization)) " => " (%.nat input) " => ")]]
(_.test "Memoization makes certain computations faster."
(io.run
(do io.monad
[[fast-time fast-output] (..time fast input)
[slow-time slow-output] (..time slow input)
#let [_ (log! (format prefix " memoized = " (%.duration fast-time)))
_ (log! (format prefix "non-memoized = " (%.duration slow-time)))]]
(wrap (and (n.= fast-output slow-output)
(:: duration.order < slow-time fast-time))))))))))
|
