Given

```
data Empty a
```

we have

```
data Free Empty a
= Pure a
-- the Free constructor is impossible!
```

which is isomorphic to

```
data Identity a
= Identity a
```

Given

```
data Identity a = Identity a
```

we have

```
data Free Identity a
= Pure a
| Free (Identity (Free Identity a))
```

which is isomorphic to

```
data Deferred a
= Now a
| Later (Deferred a)
```

or equivalently (if you promise to evaluate the fst element first) `(Nat, a)`

, aka `Writer Nat a`

, with

```
data Nat = Z | S Nat
data Writer Nat a = Writer Nat a
```

Given

```
data Maybe a = Just a
| Nothing
```

we have

```
data Free Maybe a
= Pure a
| Free (Just (Free Maybe a))
| Free Nothing
```

which is equivalent to

```
data Hopes a
= Confirmed a
| Possible (Hopes a)
| Failed
```

or equivalently (if you promise to evaluate the fst element first) `(Nat, Maybe a)`

, aka `MaybeT (Writer Nat) a`

with

```
data Nat = Z | S Nat
data Writer Nat a = Writer Nat a
data MaybeT (Writer Nat) a = MaybeT (Nat, Maybe a)
```

Given

```
data Writer w a = Writer w a
```

we have

```
data Free (Writer w) a
= Pure a
| Free (Writer w (Free (Writer w) a))
```

which is isomorphic to

```
data ProgLog w a
= Done a
| After w (ProgLog w a)
```

or, equivalently, (if you promise to evaluate the log first), `Writer [w] a`

.

Given

```
data Const c a = Const c
```

we have

```
data Free (Const c) a
= Pure a
| Free (Const c)
```

which is isomorphic to

```
data Either c a
= Right a
| Left c
```

Given

```
data Reader x a = Reader (x -> a)
```

we have

```
data Free (Reader x) a
= Pure a
| Free (x -> Free (Reader x) a)
```

which is isomorphic to

```
data Demand x a
= Satisfied a
| Hungry (x -> Demand x a)
```

or equivalently `Stream x -> a`

with

```
data Stream x = Stream x (Stream x)
```

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow