If you are unfamiliar with how lists are defined/represented in Haskell, here is a quick breakdown. The List type has two data constructors:
List a = Nil | Cons a (List a)
which is simplfied with syntactic sugar to
[a] = [] | a : [a]
What does this mean for us? Well, since lists expose only their first element, retrieving the first element of a list is easier than retrieving the last, and adding the beginning of a list is easier than adding to the end.
Aside from defining an anti-list, which exposes its last element (which would run into the same problem on the other end), there is no obvious solution to this in terms of creating a concrete type. Syntactic sugar is our friend, however. When Haskell (or, rather, your friendly neighborhood Haskell compiler) sees
[1,2,3], this really means
1:(2:(3:[])) when you remove the artificial sweeteners. If we wanted to add
4 to the end of this list, we would have to unwrap it until we got to the
[], and replace it with
(4:[]). For this small case, it's not a huge deal, but for much larger lists, this can be time-consuming, especially when we want to add more than one element to the end, and not all at the same time.
This is where FLists come in (the term is most likely not an actual one, but it may very well be one, I don't know). One key observation is that the
[] part of each list is completely useless, aside from bookkeeping where the list ends and allowing said appending. The key idea behind FLists is that we represent a list of values by the function that prepends those values to a list.
newtype FList a = FList { f :: [a] -> [a] }
We are using a newtype instead of a type alias so that we can create instances of various typeclasses to make this more like a list, because functions are paragon (cannot be compared), illegible (cannot be read), and obscene (cannot be shown). With this representation of a list, we can easily translate between the two, and easily join two lists in either order with little issue. Concatenating two FLists is as easy as composing the functions they hold:
append :: FList a -> FList a -> FList a
append (FList f) (FList f') = FList $ f . f'
toList :: FList a -> [a]
toList = ($[]).f
fromList :: [a] -> FList a
fromList [] = FList id
fromList (x:xs) = Flist (x:) `append` fromList xs
instance Show a => Show (FList a) where
show = show.toList
We can even implement an instance of
Eq for FList:
instance (Eq a) => Eq (FList a) where
(==) f g = (==) (f []) (g [])
The applications of this are fairly limited, but where it is applicable, it can be very useful.
The next WTFP will explore the possibilities for infinite lists in OCaml.
