A non empty list is one with at least one element, but is otherwise identical to the traditional immutable list in complexity and API. Sometimes you have a function that expects a list with at least one element in the function call. We cannot enforce the user to provide a non empty list using either the Kotlin List interface or the List class from the custom Dogs library. Here we present the NonEmptyList class that guarantees to have one or more elements.
Motivation
Consider an order-taking workflow for a manufacturing company. An order might include the customer name, the billing and shipping addresses and a number of order lines. We might consider a List to represent the order lines but a List may be empty and the integrity of a business rule may be violated if we permit an order with zero order lines.
Equally, suppose we have some function that operates on a series of one or more values given as a parameter. An obvious choice would be use a List for the parameter type and make a check within the function body that the list length exceeds zero.
We can use the Kotlin type system to represent what is valid or invalid so that the compiler can check it for us, instead of relying on runtime checks or code comments to ensure the rules are maintained. For this function a more appropriate parameter type would be NonEmptyList which, as its name suggests, contains one or more elements.
When validating user input we might consider using the Validation class from the custom library (see later). The Validation class has two concrete sub-classes Failure and Success. The Failure class carries a number of error types. Since it is meaningless to have a Failure with no errors then we use the type Failure<NonEmptyList<Error>> where Error is some error type. We discussed this in the Validation type blog.
Immutable NonEmptyList
The immutable NonEmptyList type is defined as:
class NonEmptyList<out A> internal constructor(val hd: A, val tl: List<A>)
Again, since the constructor is tagged internal, a series of factory constructor functions are provided:
assertEquals(4, cons(1, cons(2, cons(3, singleton(4)))).size())
assertEquals(1, cons(1, cons(2, cons(3, singleton(4)))).head())
assertEquals(4, cons(1, cons(2, cons(3, singleton(4)))).last())
assertEquals(9, of(1, 2, 3, 4, 5, 6, 7, 8, 9).size())
assertEquals(10, closedRange(1, 10).size())
Unlike the List class, the member function head of class NonEmptyList is a safe operation that guarantees not to throw an exception. Further, some member functions of NonEmptyList such as map deliver a NonEmptyList result, while others, such as filter, deliver a List result. This is necessary since the predicate to the filter function may not match any element of the NonEmptyList. Here are some examples that deliver Lists:
assertEquals(ListF.of(3, 4, 5), NonEmptyListF.of(1, 2, 3, 4, 5).drop(2))
assertEquals(ListF.of(), NonEmptyListF.of(1, 2, 3, 4, 5).drop(6))
assertEquals(ListF.of(2, 4), NonEmptyListF.of(1, 2, 3, 4, 5).filter(isEven))
assertEquals(ListF.of(), NonEmptyListF.of(1, 2, 3, 4, 5).filter{n -> (n > 10)})
Here are some of the many functions over NonEmptyLists:
assertEquals(3, NonEmptyListF.of(1, 2, 3, 4, 5)[2])
assertEquals(true, NonEmptyListF.of(1, 2, 3, 4, 5).contains(4))
assertEquals(15, NonEmptyListF.of(1, 2, 3, 4, 5).foldLeft(0){acc -> {el -> acc + el}})
assertEquals(
NonEmptyListF.of(false, true, false, true, false),
NonEmptyListF.of(1, 2, 3, 4, 5).map(isEven)
)
assertEquals(
NonEmptyListF.of(Pair(1, 'a'), Pair(2, 'b'), Pair(3, 'c')),
NonEmptyListF.of(1, 2, 3, 4, 5).zip(NonEmptyListF.of('a', 'b', 'c'))
)
Case Study
An important attribute of applicatives is that they compose. Since the NonEmptyList class is an applicative then it supports the fmap3 function which maps a function of three parameters across the elements of three NonEmptyLists. Suppose we have the function volume which computes the volume of a cuboid:
fun volume(length: Int, width: Int, height: Int): Int = length * width * height
Consider that we wish apply this function but each of the dimensions are in NonEmptyLists:
val lengths: NonEmptyList<Int> = of(2, 3, 4, 5)
val widths: NonEmptyList<Int> = of(6, 7)
val heights: NonEmptyList<Int> = of(7, 8, 9)
The fmap3 function has the signature:
fun <A, B, C, D> fmap3(la: NonEmptyList<A>, lb: NonEmptyList<B>,
lc: NonEmptyList<C>, f: (A) -> (B) -> (C) -> D): NonEmptyList<D>
and use it with:
val volumes: NonEmptyList<Int> = NonEmptyListF.fmap3(lengths, widths, heights, ::volume)
assertEquals(
NonEmptyListF.of(84, 96, 108, 98, 112, 126, 126, 144, 162, 147, 168, 189, 168, 192, 216, 196, 224, 252, 210, 240, 270, 245, 280, 315),
volumes
)
where the values 84, 96, 108, 98, ... are produced from 2 * 6 * 7, 2 * 6 * 8, 2 * 6 * 9, 2 * 7 * 7, ...
The code for the Dogs library can be found at:
No comments:
Post a Comment