blob: 05fb1fac6a7989c9f71cd9b0b48e1c44b9315709 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
+++
title = "Using the State monad for hash consing"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["3c3c"]
forwardlinks = ["3c3c2"]
zettelid = "3c3c1"
+++
One example is to use the State monad to remember inputs and their
results. However, there are many down sides to doing it this way. First,
this means that every function that should be memoized needs to use a
monadic type. Therefore `A -> B` is converted to `A -> M B`, where `M`
is the State monad.
This then means that every other call site needs to be changed to work
in the State monad, which is quite difficult, and makes it even harder
to reason about the code. This is because it is a deep embedding of
memoization in Coq.
|
