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
Top comments (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: