WTFP #2: OCaml ThunkLists

After roughly one and a smidge years of hiatus, I am back with the promised WTFP #2, OCaml infinite lists.

They aren't quite the same thing as the infinite lists in Haskell, due to the fact that OCaml isn't as lazy as Haskell is, but they follow a somewhat similar principle to the FLists I mentioned back in the previous WTFP. This is the definition of a Thunklist, or thunked:

type 'a thunked = Thunk of 'a * (unit -> 'a thunked)

What is this saying? Well, since it has been more than a year since I touched OCaml, I will do my best to explain.

Translating into haskell:

data ThunkList a = Thunk a (() -> ThunkList a)

You see, since the only thing that OCaml is really lazy about are functions, we define a list consisting of a head element, and a tail element that can't be bothered to get off its ass and show up right away. If we pay it a dollar (in this case, a unit or ()), it will stick its head round the corner but keep its tail hidden. And so forth.
So, what this does is basically implement artificial laziness on the second component of the list, so we can handle infinity since we never have to see it. From this point, we can define the basic list functions head and tail:

(* first element of a thunked list *)
let head : 'a thunked -> 'a =
  fun z -> match z with | Thunk (x,_) -> x

(* remainder of a thunked list *)
let tail : 'a thunked -> 'a thunked =
  fun z -> match z with | Thunk (_,th) -> th ()

and even our old friend (!!):

(* index accessor of a thunked list *)
let rec get : int -> ('a thunked -> 'a) =
  fun i -> match i with
    | 0 -> head
    | y when y > 0 -> fun xs -> get (i-1) (tail xs)
    | _ -> failwith "cannot get negative index"

But where do we go from here? Well, exploiting the laziness mentioned earlier, we can even have bidirectionally infinite lossless lists, if we could be bothered.

(* dethunk: a doubly-lazy, doubly-infinite list *)
type 'a dethunk = (unit -> 'a thunked) * 'a * (unit -> 'a thunked)

Since I am too lazy, I will leave implementing the functions you would want out of a bidirectionally infinite lossless list. I have the implementation in front of me, but I am just too lazy.

WTFP #1: Haskell FLists

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.

WTFP: Announcement

After having absolutely nothing to write about on this blog for 2 years (give or take), I am pleased to announce that I still have nothing to write about, but this time I will not let that stop me from posting.

---

I am starting a series of posts called "What the Func(tional programming)", or WTFP for short. These posts will consist of observations, insights, and delerious ramblings (mostly the last) I have regarding Functional Programming, in particular Haskell (which I am self-teaching), and OCaml (which I am taking a class in). I will try to alternate between these languages (and any other I decide to introduce) as much as possible, but if I run out of one, I might have serial posts on the other. The next two posts will be about non-standard list representations in Haskell/OCaml (respectively) that have unique features that distinguish them from the standard list representations. Stay tuned to this station. If you were able to touch that dial, I would advise against it, probably because it is unclear what that dial would do if turned.