Disclaimer
As per the previous post in this series, in the process of helping out the community of people 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 faster, more obvious, or easier approach is readily available. Jumping ahead from exercise 1 straight to exercise 6.
Exercise 6: Find out whether a list is a palindrome
A definition of a palindrome
can be found on Wikipedia.
Could you follow a "unison workflow" this time?
I previously touched on two ucm
commands: find
and view
, which allow finding functions in the current codebase, and seeing their implementation as stored by the codebase manager.
In this post I will do showcase the Unison workflow (or my understanding/interpretation of it), by means of the add
, update
, test
and potentially other ucm
commands.
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 on your targetcodebase
: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
, under thecodebase
location:ucm
will pick up any changes to thescratch file
, and provide output as necessary.
Why Unison?
One of the selling points of Unison
is that code is content-addressed and immutable
. I would advise taking a close look into the guide for a more in-depth explanation.
In practice and in short: names
do not matter. The compiler keeps track of the abstract syntax tree
representation of the code only, addressing the hashes
and not the names
of other functions and values.
No more code formatting or renaming vals and functions. To begin.
Can you write tests beforehand?
Fan of TDD
? Let's begin by adding a number of lists some being and some not being palindromes.
passing: [[Nat]]
passing =
[
[],
[1],
[1, 1],
[1, 1, 1],
...
[1, 2, 3, 3, 2, 1] -- you get the idea
]
failing: [[Nat]]
failing =
[
[1, 2],
[1, 1, 2],
...
[1, 1, 1, 1, 2, 2] -- you also get the idea
]
The signature of palindrome
as well as a default implementation are required as a minimum for the code and unit tests to compile.
palindrome: [a] -> Boolean
palindrome xs = true
Before doing anything else, let's save the scratch file and what ucm
thinks:
⍟ These new definitions are ok to `add`:
failing : [[Nat]]
palindrome : [a] -> Boolean
passing : [[Nat]]
No need to see (or care) about these definitions anymore, and the flow is to add
them, clear the scratch file, and proceed.
Note: tests would normally be added under a dedicated namespace. Code organisation is beyond the scope of this post (for now at least).
Suggestion: If you'd rather keep code around it can be converted to comments, for example, and to prevent constant views
, comment lines out inline by --
at the beginning of each line, or by adding the comment line: ---
. Anything under ---
is not taken into account by ucm
.
You still haven't written any tests though...
Indeed I have not. I would rather not have to write each test separately, so let's add a quick helper that applies palindrome
to each member of each list, and aggregates the results to one Boolean
status.
success: ([a] -> Boolean) -> [[a]] -> Boolean
success func inputs =
foldl (status nextInput -> (func nextInput) && status) true inputs
failure: ([a] -> Boolean) -> [[a]] -> Boolean
failure func inputs =
foldl (status nextInput -> (func nextInput) || status) false inputs
To the above, after removing the empty ability symbols
, for clarity, ucm
responds with the following :
⍟ These new definitions are ok to `add`:
failure : ([a] -> Boolean) -> [[a]] -> Boolean
success : ([a] -> Boolean) -> [[a]] -> Boolean
Once again the flow is to add
the new definitions, clear the scratch file, and proceed to finally write some test cases!
Tests please!
palindrome
is parametric on type a
, so for ease of testing, the tests can use [Nat]
. Writting the tests in the scratch file
is straightforward and follows the guide.
use tests.v1
test> passing.loop = run(expect (success palindrome passing == true))
test> failing.loop = run(expect (failure palindrome failing == false))
To the above ucm
responds:
⍟ These new definitions are ok to `add`:
failing.loop : [Result]
passing.loop : [Result]
4 | test> passing.loop = run(expect (success palindrome passing == true))
✅ Passed : Passed 1 tests. (cached)
5 | test> failing.loop = run(expect (failure palindrome failing == false))
🚫 FAILED (cached)
The tests (as well as the success
and failure
functions) might look attrocious to a more trained eye, but in the spirit of good enough and not focusing on testing too heavily, now is a good time to add
, clear and proceed with implementing palindrome
.
Implement all the things!
The easiest way to implement palindrome
is to follow the definition of the input reads the same backward as forward
:
palindrome xs = xs == reverse (xs)
to which ucm
will respond:
⍟ These new definitions will replace existing ones of the same name and are ok to `update`:
palindrome : [a] -> Boolean
Before updating
the definition of palindrome
, the second test case is failing, as the original definition is hardcoded:
.> test
Cached test results (`help testcache` to learn more)
◉ passing.loop : Passed 1 tests.
✗ failing.loop
🚫 1 test(s) failing, ✅ 1 test(s) passing
After updating
the implementation, however, it's a whole new picture:
.> update
⍟ I've updated to these definitions:
palindrome : [a] -> base.Boolean
✅
.> test
✅
New test results:
◉ passing.loop : Passed 1 tests.
◉ failing.loop : Passed 1 tests.
✅ 2 test(s) passing
Not bad Unison
, not bad at all. However it gets better:
.> test
Cached test results (`help testcache` to learn more)
◉ passing.loop : Passed 1 tests.
◉ failing.loop : Passed 1 tests.
✅ 2 test(s) passing
After updating palindrome
, the very first invocation of the test
command actually runs the tests. With the test definitions being viewable
at any time, subsequent runs will only show cached results. No updates to any code, means no need to run any tests.
Could we try another approach?
Let's see what base.List.halve
does:
.> view base.List.halve
base.List.halve : [a] -> ([a], [a])
base.List.halve s =
n =
use Nat /
List.size s / 2
(List.take n s, List.drop n s)
The middle index n
is specified as s / 2
. This results in lists of an even number of elements being split to two halves of equal length. However, lists of an odd number of elements will result in the second half being longer by one element.
.>
⧩
([1], [2, 1])
⧩
([1, 2], [3, 2, 1])
One approach could be: pick the middle element (2
and 3
in the examples above respectively), push it to the end of the first half, then compare the first half, with the reverse
of the second half.
But it feels a bit brittle...
Debatable, but agreed. A more robust approach might be to implement a slightly different flavour of halving
, specifically tailored to the needs of palindrome
. A list of even elements will still be split into two lists of equal length, but in the case of an odd number of elements, the two lists will both contain the middle element.
This new version of halve
, just like in the base.List
flavour of halve
will still rely on base.List.slice
. The intention is to indeed add
a new function, and not change the halve
implementation by means of updating
it.
.> view base.List.slice
base.List.slice : Nat -> Nat -> [a] -> [a]
base.List.slice start stopExclusive s =
List.take (Nat.drop stopExclusive start) (List.drop start s)
halve': [a] -> ([a], [a])
halve' xs =
s = size xs
m = s / 2
if (s `mod` 2 == 1)
then ((slice 0 (m + 1) xs), (slice m s xs))
else halve xs
test> halve'.empty = run( expect ( halve' [] == ([], [])))
test> halve'.one = run( expect ( halve' [1] == ([1], [1])))
test> halve'.two = run( expect ( halve' [1, 1] == ([1], [1])))
test> halve'.three = run( expect ( halve' [1, 2, 3] == ([1, 2], [2, 3])))
test> halve'.four = run( expect ( halve' [1, 2, 3, 4] == ([1, 2], [3, 4])))
With the new halve'
and relevant tests added
, and tests passing, palindrome
can be reworked. Clearing the scratch file, let's start rewriting palindrome
:
palindrome: [a] -> Boolean
palindrome xs =
t = halve' xs
at1 t == (reverse . at2) t
.>
I found and typechecked these definitions in ~/unison/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`:
palindrome : [a] -> Boolean
Updating the definition and running the tests, the new version does indeed still pass all tests.
And what else?
One could also:
-
zip
the input with itsreverse
andfoldl
over the tuples, is directly equivalent to the original implementation. - Using
base.List.range
, produce a list of all indexes,reverse
it thenzip
, to have a list of pairs of elements to be checked for equality. Then access the elements at(0, n), (1, n - 1), .. (n, 0)
and compare them, at the added cost of having to deal with each access returningOptional a
. Probably not the easiest or most testable of approaches. - Compare the first and last element, without the imperative indexing or direct element access, which can be achieved via pattern matching with the help of an inner function:
palindrome: [a] -> Boolean
palindrome xs =
go as bs = case (as, bs) of
([], []) -> true
(head +: tail, init :+ last) -> head == last && go tail init
(head +: [], [] :+ last) -> head == last
go xs xs
As mentioned in the previous post, +:
constructs a list from a head element +: tail list
whereas :+
constructs a list from init list :+ the last element
. The above could be coded without go
, by matching on xs
twice (case (xs, xs) of ...
).
Are the tests still passing?
Yes they are, and after the initial upfront investment in time and effort, they made up for it by allowing me to:
- have confidence in the continued correctness of
palindrome
- refactor incrementally, multiple times.
And what about all of those famous palindromes?
Well spotted, all yours:
use base.Text
test> test.palindromes.greek =
run( expect( ( (palindrome . toCharList) "ΝΙΨΟΝΑΝΟΜΗΜΑΤΑΜΗΜΟΝΑΝΟΨΙΝ") == true))
test> test.palindromes.latin =
run( expect( ( (palindrome . toCharList) "SATORAREPOTENETOPERAROTAS") == true))
test> test.palindromes.english1 =
run( expect( ( (palindrome . toCharList) "ablewasiereisawelba") == true))
test> test.palindromes.english2 =
run( expect( ( (palindrome . toCharList) "amanaplanacanalpanama") == true))
test> test.palindromes.english3 =
run( expect( ( (palindrome . toCharList) "neveroddoreven") == true))
Notes!
- A more thorough explanation of how
foldl
works can be found in the previous post. -
success
/failure
can be very easily written as a single function: take this as an exercise. 😉 -
unison
also comes with a thorough testing framework which you can locate withfind
andview
underbase.test.*
. There are probably better ways to aggregate over a number of tests. - A
delete
ucm
command can be used to delete no longer needed functions and values from the codebase. - And as I found out after a very helpful response to my question from Mitchell Rosen, you can
delete.namespace target.namespace.here
to get rid of all of the tests above for example. - If it all goes wrong:
undo
is always an option!
Top comments (0)