#### Disclaimer

I decided to join the community of people currently helping `alphatest`

the `Unison`

programming language. At this point in time, the standard library is actively being worked on. I will embark on solving the `99 Haskell problems`

in `unison`

, and try and make implementation notes, tailored for a beginner friendly audience. There is little expectation on my part that I will actually make it all the way to 99.

Some familiarity with concepts like recursion, tail recursion, pattern matching and functional programming might be necessary to follow the code. I have made the effort on my part to embed relevant links, as the post progresses, while at the same time removing `abilities`

from the type signatures. One of the points of the `99 exercises`

is to try as many alternative implementations: I will attempt to go out of my way and explore alternatives, even if a faster, more obvious, or easier approach is readily available.

#### Exercise 1: Find the last element of a list

##### So what can I work with?

`unison`

has a unique approach to type declarations: types are identified by their hash, and not their name. As per the snippet here, I am using `Maybe/Just/Nothing`

for the `Option a`

type.

As of `ucm release 1g`

a quick `find`

on `base.List`

reveals the following:

```
.> find base.List
base.List.++ base.List.drop base.List.insert base.List.slice base.List.unsnoc
base.List.+: base.List.empty base.List.join base.List.snoc base.List.zip
base.List.:+ base.List.flatMap base.List.map base.List.sortBy base.List
base.List.at base.List.foldb base.List.range base.List.take
base.List.cons base.List.foldl base.List.replace base.List.uncons
base.List.diagonal base.List.halve base.List.reverse base.List.unfold
base.List.distinct base.List.indexed base.List.size base.List.unsafeAt
```

Coming from other programming languages that implement cons lists, my expectation was that the code would be more or less implemented as a pattern match, involving use of the cons constructor (`::`

). However, at the time of writing, the language reference around pattern matching on lists was not available.

#####
Simple recursion using `uncons`

Let's briefly see what `uncons`

does:

```
.> find base.List.uncons
1. base.List.uncons : [a] -> Maybe (a, [a])
```

Given a list of `as`

, `uncons`

returns a `Maybe (a, [a])`

tuple of the head and tail of the list (the tail itself being a list). Using `uncons`

, the first recursion clause will be `Nothing`

for an empty list. There is no last element in this case, so the function returns `Nothing`

. In the case of a head element followed by a tail, the recursion ends when, peeking into the tail, it is found empty, the `head`

thus being the last element of the list. If the tail does contain more elements, the function recurses into the tail, till a result is found.

```
last: [a] -> Maybe a
last xs = case uncons xs of
Nothing -> Nothing
Just (a, []) -> Just a
Just (a, as) -> last as
```

##### But does my function work? (aka unit and property tests)

Using the (very straightforward turns out) testing framework of `unison`

, some quick tests prove that the function works as anticipated:

```
test> last.empty = run( expect( last [] == None))
test> last.nonEmpty = run( expect( last [1] == Just 1))
test> last.prop.last =
go _ = a = !(list nat)
b = !nat
expect( (last (a ++ [b])) == Just b)
runs 100 go
test> last.empty = run( expect( last [] == None))
✅ Passed : Passed 1 tests. (cached)
test> last.nonEmpty = run( expect( last [1] == Just 1))
✅ Passed : Passed 1 tests. (cached)
go _ = a = !(list nat)
✅ Passed : Passed 100 tests. (cached)
```

#####
I think there's more in `base.List`

Turns out there's another interesting function in base.List, `unsnoc`

, which I actually at first glance overlooked:

```
.> find base.List.unsnoc
1. base.List.unsnoc : [a] -> Maybe ([a], a)
```

Given a list of `as`

, `unsnoc`

(maybe) breaks the list into: a list containing all but the last element, and the last element. At which point the `last`

element, needs to just be extracted from the tuple:

```
last: [a] -> Maybe a
last xs = map at2 (unsnoc xs)
```

##### How about a more 'formal' or 'generic' way of doing any of this?

The `fold pattern`

is used to generalize over recursion (and tail recursion, more on these to follow).

Let's briefly see what `foldb`

does:

```
.> find base.List.foldb
1. base.List.foldb : (a -> b) -> (b -> b -> b) -> b -> [a] -> b
.> view base.List.foldb
base.List.foldb : (a -> b) -> (b -> b -> b) -> b -> [a] -> b
base.List.foldb f op z as
```

In a (very) generic way, given a function `f`

to apply, and an operator `op`

, `foldb`

will convert a list of `a`

to a list of `b`

, using a default term `z`

as the beginning (and end, if the list is empty).

Caring only to get the last element of a list, the default `z`

is `Nothing`

, the `f`

provides a way to box elements in a `Just`

and the `op`

only cares to keep track of the last element seen:

```
(a -> Maybe a) -> Just
(Maybe a -> Maybe a -> Maybe a) -> (x -> y -> y)
Maybe a -> Nothing
[a] -> xs
b
last: [a] -> Maybe a
last xs = foldb Just (x -> y -> y) Nothing xs
```

##### How about 'tail recursion'?

Quick mention: If a function can be written in terms of `recursion`

, in certain programming languages, the compiler can optimise the calls to an iteration, if the function is rewritten in a `tail recursive`

manner.

The intention at this point is not to assess whether the compiler indeed optimises tail recursive calls, but to reimplement the definition of `last`

.

Let's briefly see what `foldl`

does:

```
.> find base.List.foldl
1. base.List.foldl : (b -> a -> b) -> b -> [a] -> b
.> view base.List.foldl
base.List.foldl : (b -> a -> b) -> b -> [a] -> b
base.List.foldl f z as
```

In an analogous to `foldb`

manner, `foldl`

will require a `z`

term, as well as an `f`

, which in this case keeps track of the last element. Notice that boxing in a `Just`

, happens as the elements are iterated over.

```
(b -> a -> b) -> (x -> y -> Just y)
b -> Nothing
[a] -> xs
b
last: [a] -> Maybe a
last xs = foldl (x -> y -> Just y) Nothing xs
```

#####
The `unison`

way!

I reached out to the `alphatesting`

slack channel for `unison`

, and Paul Chiusano pointed out that the `base.List`

data structure in `unison`

is implemented in terms of a `finger tree`

. There is no need to go over the entire list, since the finger tree provides constant amortized time access to the (first and) last element.

```
.> find base.List.size
1. base.List.size : [a] -> Nat
.> find base.List.at
1. base.List.at : Nat -> [a] -> Maybe a
```

`List.size`

returns a `Nat`

of the size of the list, which then needs to be `dropped`

by one, since the list is indexed from `0`

to `(size - 1)`

.

```
last: [a] -> Maybe a
last xs = List.at (List.size xs `drop` 1) xs
```

##### So what would be the "suggested approach"?

`unsnoc`

, mentioned above, is probably the best balance between a convenient return signature, `O(1)`

access to either end of the underlying finger tree, simple and straightforward use at the callsite. And for the curious ones, here's a quick peak into what it actually does:

```
.> view base.List.unsnoc
base.List.unsnoc : [a] -> Maybe ([a], a)
base.List.unsnoc as =
i = List.size (List.drop 1 as)
case List.at i as of
None -> None
Just a -> Just (List.take i as, a)
```

##### Final note:

I have avoided a more advanced coding style on purpose. For reference, lambdas parameters to be ignored can be substituded by `_`

, and function arguments (like `xs`

) can be dropped on both the left and right hand side of the definition.

```
last = foldb Just (_ -> y -> y) Nothing
last' = foldl (_ -> y -> Just y) Nothing
```

## Discussion (1)

Thanks very much for this tutorial! I am trying to learn Unison, so this helps. But the versions with the fold patterns where still above my understanding level. I also don't understand the use of

`drop`

Any suggestions where I could find a simple explanation?

Some remarks:

The ' in the last line should be dropped: last' = foldl (_ -> y -> Just y) Nothing

I am using release M1m: