How to Make a Thing in Haskell, Part 8: Zipping

I’ve completed skellect, so it’s time to catch up and post my thoughts on the rest of its implementation. (It’s kinda hard to be disciplined about writing and posting as you go! I hadn’t expected that challenge.) representing state and actually putting the underlying algorithms to use.

The data structure I use is what will be manipulated by ^N and ^P in the final product to choose different elements of the current filtered list. Then, it will be passed to some rendering function to produce output on tty. The functions associated with this data structure will be:

In my initial, busted implementation, I just used a record containing a list and an integer indicating what value was selected. The problem with this representation of the data is that the integer and list have to be managed separately and kept in sync. I had a hard time only defining functions that kept the integer within the bounds of the list, for instance; nothing prevents you from indexing into the 10th item of a 9-element list.

Another, more elegant solution could be to use Either or define a similar choice-y type:

data Selection a = Selected a | Unselected a deriving Show

and the next operation could be defined by pattern matching over a list of Selection Strings:

next :: [Selection a] -> [Selection a]
next (Selected x : Unselected y : zs) = Unselected x : Selected y : zs
next (Unselected x : zs)              = Unselected x : next zs
next xs                               = xs

Kind of more elegant. But there’s a flaw: this representation allows for meaningless states, like lists where there are two Selected values. I feel like the datatype for representing the state of the list should keep me from having to ask what such a state could mean.

After letting the question sit for a while, I realized that I could represent the data structure in three parts: the selection itself, and lists of elements before and after the selection. That way, the type checker would enforce that exactly one valid element is selected, and it’d be easier to reason about correctly moving the selection: it’s just a matter of shuffling elements from the end of the before list and the beginning of the after list. Then I realized that this is a simple (one of the simplest?) form of a data structure that I’d heard of, but not yet wrapped my head around: the zipper. So, time to implement my first zipper!

In my first iteration, I implemented the data structure and fromList like this:

data SelectionList a =
    SelectionList { before    :: [a]
                  , selection ::  a
                  , after     :: [a] }

fromList :: [a] -> SelectionList a
fromList (x:xs) = SelectionList [] x xs

However, there’s a problem here: how do you represent an empty SelectionList? before and after can be [], but the type checker won’t allow an empty selection. Since I’m all about optional types now, I first reached for a Maybe:

data SelectionList a =
    SelectionList { before    :: [a]
                  , selection :: Maybe a
                  , after     :: [a] }

fromList :: [a] -> SelectionList a
fromList []     = SelectionList [] Nothing []
fromList (x:xs) = SelectionList [] (Just x) xs

But that’s kinda gross, in the same way keeping an index into a list of selections is gross. I’d have to make sure that the relationship between the list and the selection stayed valid. The type checker would allow values like

sl = SelectionList [1, 2] Nothing [3, 4]

which creates an invalid relationship between selection and the rest of the list. Just like an empty SelectionList shouldn’t allow you to have anything selected, a non-empty SelectionList should require you to always have something selected. The way I avoided that is by creating multiple constructors for the SelectionList type:

data SelectionList a =
    SelectionList {before    :: [a]
                  ,selection ::  a
                  ,after     :: [a] } |
    EmptySelectionList

This allows a cleaner return value for fromList:

fromList :: [a] -> SelectionList a
fromList [] = EmptySelectionList
fromList (x:xs) = SelectionList [] x xs

Since next returns its argument when the after list is empty, this representation allows a simple and elegant implementation here as well:

next :: SelectionList a -> SelectionList a
next (SelectionList b s (a:as)) =
    SelectionList (b ++ [s]) a as
next s = s

prev? A little less so:

prev :: SelectionList a -> SelectionList a
prev sl@(SelectionList b s a) = case b of
    [] -> sl
    _  -> SelectionList (init b) (last b) (s : a)
prev sl = sl

Since you can’t pattern match for the end of the list, this function has to check that b is non-null before operating over the data. It has to explicitly handle the empty list, which is unfortunate.

Luckily, there’s another standard library data structure that allows for pattern matching against both ends and can, with a little elbow grease, be dropped right in for list: Seq. After importing Sequence as S:

data SelectionSeq a =
    SelectionSeq { before    :: S.Seq a
                 , selection :: a
                 , after     :: S.Seq a } |
    EmptySelectionSeq

fromList :: [a] -> SelectionSeq a
fromList []     = EmptySelectionSeq
fromList (x:xs) = SelectionSeq (S.fromList []) x (S.fromList xs)

Fair enough. What are next and prev like?

next :: SelectionSeq a -> SelectionSeq a
next sl@(SelectionSeq b s a) = case viewl a of
    s' :< a' -> SelectionSeq (b |> s) s' a'
    EmptyL -> sl
next sl = sl

prev :: SelectionSeq a -> SelectionSeq a
prev sl@(SelectionSeq b s a) = case viewr b of
    b' :> s' -> SelectionSeq b' s' (s <| a)
    EmptyR -> sl
prev sl = sl

That’s… not as nice as I’d hoped. All the operations are constant-time, true, but there are more cases to match against. And we’ve added not one, but two, new types to the mix: ViewL and ViewR for left and right views of each Seq.

Finally, I looked back at Learn You a Haskell’s chapter on zippers, which reminded me that list traversal can be represented as manipulation of with two stacks, one reversed!

data ListZipper a =
    ListZipper {before    :: [a]
               ,selection ::  a
               ,after     :: [a]} |
    EmptyListZipper deriving (Show, Eq)

fromList :: [a] -> ListZipper a
fromList []     = EmptyListZipper
fromList (x:xs) = ListZipper [] x xs

fromLists :: [a] -> a -> [a] -> ListZipper a
fromLists b = ListZipper (reverse b)

I still include the selection element because I want to continue requiring an element to be selected. Any value that can be constructed is a valid state for a ListZipper.

While I like the implementations of these functions, the ListZipper interface is not as nice as it could be. This is one place where the tools offered by object-oriented languages come in handy. In an OO environment, I could let the underlying representation of the after list be reversed, but present an interface that returns the list in its proper order. I know that’s possible in Haskell, but most of the writing I’ve found online about hiding representations involves lenses, which is a complexity I don’t want to get into just yet. I think fixing it is a task for another time. If you have any insight about data hiding in Haskell, I’d love to hear your thoughts!