I decided to join the community of people currently helping
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.
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.
ucm release 1g a quick
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.
Let's briefly see what
.> find base.List.uncons 1. base.List.uncons : [a] -> Maybe (a, [a])
Given a list of
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
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  == 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  == Just 1)) ✅ Passed : Passed 1 tests. (cached) go _ = a = !(list nat) ✅ Passed : Passed 100 tests. (cached)
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
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)
fold pattern is used to generalize over recursion (and tail recursion, more on these to follow).
Let's briefly see what
.> 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
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
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
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
Let's briefly see what
.> 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
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
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
(size - 1).
last: [a] -> Maybe a last xs = List.at (List.size xs `drop` 1) xs
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)
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