Disclaimer
As per the previous posts in this series, in the process of helping out the community alphatesting
the Unison
programming language, I am solving the 99 Haskell problems
in Unison
and making notes, tailored for a beginner-friendly audience.
One of the points of the 99 exercises
is to try alternative implementations. I will go out of my way (within reason) and explore such alternatives even if a faste, more obvious or easier approach is readily available.
Understanding of some concepts of functional programming might be required and the intention of this series is to be tailored to a beginner-level audience. For all concepts mentioned in the post I have made the effort to embed relevant hyperlinks. In the event you encounter something you don't fully understand, but does come with a hyperlink-hint feel free to either read to the end then search, or why not get a quick glimpse of the term before you proceed.
Exercise 8: Eliminate consecutive duplicates of list elements.
Can I play too?
To follow along you will need:
- the Unison codebase manager
ucm
. Optionally in the$PATH
. - A new project created with
ucm -codebase path init
. -
ucm
running your project undercodebase
by means of:ucm -codebase path
. - The
standard library
(calledbase
), cloned from insideucm
:pull https://github.com/unisonweb/base .base
. - An editor of your choice to open
scratch.u
undercodebase
:ucm
will tell you the folder in which it will pick up any changes to thescratch file
, and provide output as necessary.
So how do we know this thing will work?
Why don't we write some tests first. The function we are trying to write will be called compress
by convention and will reduce a list of elements to a list of maybe less elements. It can directly be placed in the base.List
namespace
, by adding the path to the namespace before the definition, but that is not necessary.
base.List.compress: [a] -> [a]
base.List.compress as = []
test> tests.compress.empty =
run ( expect ( base.List.compress [] == [] ))
test> tests.compress.nonCompressable1 =
run ( expect ( base.List.compress [1] == [1] ))
test> tests.compress.nonCompressable2 =
run ( expect ( base.List.compress [1, 2] == [1, 2] ))
test> tests.compress.nonCompressable3 =
run ( expect ( base.List.compress [1, 2, 3] == [1, 2, 3] ))
test> tests.compress.compressable1 =
run ( expect ( base.List.compress [1, 1, 1, 2, 2, 3] == [1, 2, 3] ))
test> tests.compress.compressable2 =
run ( expect ( base.List.compress [1, 2, 2, 3] == [1, 2, 3] ))
test> tests.compress.compressable3 =
run ( expect ( base.List.compress [1, 1] == [1] ))
test> tests.compress.example =
run(
expect(
(base.List.compress [?a, ?a, ?a, ?a, ?b, ?c, ?c, ?a, ?a, ?d, ?e, ?e, ?e, ?e] ==
[?a, ?b, ?c, ?a, ?d, ?e])
)
)
Note: compress
is directly coded into the base.List
namespace above, and all tests point to it by full path. This is equivalent to first using the cd .base.List
command, to move namespace, then coding compress
without a namespace in the declaration and implementation.
I found and typechecked these definitions in :scratch.u. If
you do an `add` or `update`, here's how your codebase would
change:
⍟ These new definitions are ok to `add`:
base.List.compress : [a] -> [a]
tests.compress.compressable1 : [Result]
tests.compress.compressable2 : [Result]
tests.compress.compressable3 : [Result]
tests.compress.empty : [Result]
tests.compress.example : [Result]
tests.compress.nonCompressable1 : [Result]
tests.compress.nonCompressable2 : [Result]
tests.compress.nonCompressable3 : [Result]
Now evaluating any watch expressions (lines starting with
`>`)... Ctrl+C cancels.
5 | run ( expect ( base.List.compress [] == [] ))
✅ Passed : Passed 1 tests.
8 | run ( expect ( base.List.compress [1] == [1] ))
🚫 FAILED
11 | run ( expect ( base.List.compress [1, 2] == [1, 2] ))
🚫 FAILED
14 | run ( expect ( base.List.compress [1, 2, 3] == [1, 2, 3] ))
🚫 FAILED
17 | run ( expect ( base.List.compress [1, 1, 1, 2, 2, 3] == [1, 2, 3] ))
🚫 FAILED
20 | run ( expect ( base.List.compress [1, 2, 2, 3] == [1, 2, 3] ))
🚫 FAILED
23 | run ( expect ( base.List.compress [1, 1] == [1] ))
🚫 FAILED
26 | run(
🚫 FAILED
The test cases above contain the following inputs:
- the empty list
[]
- a non compressible list containing one, two and three elements
- a compressible list beginning with a compressible sequence, and containing a compressible sequence afterwards
- a compressible list beginning with a non compressible sequence, followed by a compressible one
- the
example
from the problem definition, which on closer scrutiny and in good humour almost provides more coverage than the previous cases put together.
So what next?
ucm
agrees with the types and syntax so far so we can add
these definitions, and clear the scratch file.
.> add
⍟ I've added these definitions:
base.List.compress : [a] -> [a]
tests.compress.compressable1 : [Result]
tests.compress.compressable2 : [Result]
tests.compress.compressable3 : [Result]
tests.compress.empty : [Result]
tests.compress.example : [Result]
tests.compress.nonCompressable1 : [Result]
tests.compress.nonCompressable2 : [Result]
tests.compress.nonCompressable3 : [Result]
So can we now implement compress
?
Let's have a first try, while relying on list look-ahead. Previously I would view
a definition on the terminal and then copy-paste that into the scratch file. I will from now on use the edit
command, so that ucm
will do this for me.
base.List.compress: [a] -> [a]
base.List.compress as = case as of
[] -> []
[x] -> [x]
[x, y] ++ rest ->
if (x == y) then base.List.compress (y +: rest)
else x +: base.List.compress (y +: rest)
I found and typechecked these definitions in :scratch.u. If
you do an `add` or `update`, here's how your codebase would
change:
⍟ These new definitions will replace existing ones of the
same name and are ok to `update`:
base.List.compress : [a] -> [a]
Now evaluating any watch expressions (lines starting with
`>`)... Ctrl+C cancels.
If the input is the empty list there is nothing to be done and compress
returns the empty list. Alternatively the (x +: (y +: rest))
clause matches on a list of at least two elements, so it can proceed to check these two elements. If they are equal y
is a duplicate of x
, and the next function call will have input of y +: rest
so as not to completely discard the x|y
element. If they are not equal, x
is not discarded and equally y
is not discarded either. Notice that I jumped ahead to a list of two
elements: there is a remaining clause to be matched which I am also adding at this time: [x] -> [x]
. A list containing a single element, just like the empty list, is left intact.
My first take of the function above, give or take some minor attempts to get the syntax right, was using the pattern (x +: (y +: rest))
to refer to a list of at least two elements. After a comment by Paul Chiusano
, turns out the same can be coded as [x, y] ++ rest
, which saves some bracket noise.
.> update
⍟ I've updated to these definitions:
base.List.compress : [a] -> [a]
✅
No conflicts or edits in progress.
.> test
✅
New test results:
◉ tests.compress.compressable1 : Passed 1 tests.
◉ tests.compress.compressable3 : Passed 1 tests.
◉ tests.compress.compressable2 : Passed 1 tests.
◉ tests.compress.example : Passed 1 tests.
◉ tests.compress.nonCompressable2 : Passed 1 tests.
◉ tests.compress.nonCompressable3 : Passed 1 tests.
◉ tests.compress.nonCompressable1 : Passed 1 tests.
◉ tests.compress.empty : Passed 1 tests.
✅ 8 test(s) passing
Tip: Use view tests.compress.compressable1 to view the source
of a test.
With the function under test updated the tests have "new results". Note however that running the test
command again does not rerun any tests, but shows cached tests results, as long as the function under test has not been updated since the last run.
So can we do another one? With less pattern matching?
There might be quite a few alternatives worth exploring and we can begin by looking into an iterative approach using foldl
.
First a reminder of the signature and implementation of foldl
:
.> view base.List.foldl
base.List.foldl : (b ->{𝕖} a ->{𝕖} b) -> b -> [a] ->{𝕖} b
base.List.foldl f b as =
go b i =
case List.at i as of
None -> b
Some a ->
use Nat +
go (f b a) (i + 1)
go b 0
Going over each element of the list while using an accumulator, if the last element encountered matches the current element then it can be discarded, otherwise this element is appended to the accumulator and will be the basis of comparison in the next iteration.
base.List.compress: [a] -> [a]
base.List.compress as =
f acc elem = case acc of
[] -> [elem]
(init :+ last) -> if (last == elem) then acc else (acc :+ elem)
foldl f [] as
I found and typechecked these definitions in :scratch.u. If
you do an `add` or `update`, here's how your codebase would
change:
⍟ These new definitions will replace existing ones of the
same name and are ok to `update`:
base.List.compress : [a] -> [a]
Now evaluating any watch expressions (lines starting with
`>`)... Ctrl+C cancels.
After updating compress
, tests are still passing.
.> test
✅
New test results:
◉ tests.compress.example : Passed 1 tests.
◉ tests.compress.empty : Passed 1 tests.
◉ tests.compress.nonCompressable3 : Passed 1 tests.
◉ tests.compress.compressable3 : Passed 1 tests.
◉ tests.compress.nonCompressable2 : Passed 1 tests.
◉ tests.compress.nonCompressable1 : Passed 1 tests.
◉ tests.compress.compressable2 : Passed 1 tests.
◉ tests.compress.compressable1 : Passed 1 tests.
✅ 8 test(s) passing
Tip: Use view tests.compress.example to view the source of a
test.
Are there more alternative approaches?
Yes there are: one using dropWhile
(not part of the Unison
base
library yet) and one using group
(also not part of base
yet).
Care to go ahead regardless?
Using "dropWhile"
There are probably multiple ways to implement dropWhile
or in other words a function that given a predicate, will keep dropping elements from the head of the list for as long as the predicate holds. For example:
dropWhile (x -> x < 3) [1, 2, 3, 4, 1, 2] -> [3, 4, 1, 2]
The straightforward way is to just implement it as per its definition, without relying on an abstraction.
base.List.dropWhile: (a -> Boolean) -> [a] -> [a]
base.List.dropWhile pred as =
case as of
[] -> []
h +: t ->
if pred h then dropWhile pred t
else as
I found and typechecked these definitions in :scratch.u. If
you do an `add` or `update`, here's how your codebase would
change:
⍟ These new definitions are ok to `add`:
dropWhile : (a ->{𝕖} Boolean) ->{𝕖} [a] ->{𝕖} [a]
Now evaluating any watch expressions (lines starting with
`>`)... Ctrl+C cancels.
For dropWhile
the predicate is tested and if it is false there are no items to drop. On the other hand if it is true then the head is dropped and dropWhile
recurses into the remaining elements of the tail, using the same mechanism.
So finally compress
can be implemented in terms of dropWhile
as follows:
base.List.compress: [a] -> [a]
base.List.compress as =
case as of
[] -> []
h +: t ->
dropped = dropWhile (x -> x == h) t
h +: compress dropped
I found and typechecked these definitions in :scratch.u. If
you do an `add` or `update`, here's how your codebase would
change:
⍟ These new definitions will replace existing ones of the
same name and are ok to `update`:
base.List.compress : [a] -> [a]
Now evaluating any watch expressions (lines starting with
`>`)... Ctrl+C cancels.
In this version compress firstly acts as a means of breaking the list down to the head +: tail
clause, which then allows the remaining elements of tail to be checked for equality with head and dropped if matching. Once dropWhile
finishes filtering after the current head compress
recurses into the remaining elements of the dropped
intermediate result list.
.> update
⍟ I've updated to these definitions:
base.List.compress : [a] -> [a]
✅
No conflicts or edits in progress.
.> test
✅
New test results:
◉ tests.compress.nonCompressable1 : Passed 1 tests.
◉ tests.compress.compressable3 : Passed 1 tests.
◉ tests.compress.nonCompressable2 : Passed 1 tests.
◉ tests.compress.compressable1 : Passed 1 tests.
◉ tests.compress.empty : Passed 1 tests.
◉ tests.compress.nonCompressable3 : Passed 1 tests.
◉ tests.compress.example : Passed 1 tests.
◉ tests.compress.compressable2 : Passed 1 tests.
✅ 8 test(s) passing
Tip: Use view tests.compress.nonCompressable1 to view the
source of a test.
Using "group"
Feel free to experiment with this one which I will describe but not code. Given a function that "groups" same elements into lists, you can run group
on the input and end up with a list of lists of same elements. Collecting the head of each of those lists will give you a neat solution.
(For those who are a bit more advanced, or curious for more detail, group
could be implemented in terms of groupBy
(spoiler here), which in turn could be implemented in terms of span
(spoiler here))
Thanks for reading!
Note:
A great many thanks to Daniel Skinner for reviewing and commenting the original draft of this post.
Top comments (0)