This post is a long-form response to a question on Reddit, which asked:

I just started learning haskell, and the take function confuses me.

e.g

`take 10 [1,2,3,4,5]`

will yield`[1,2,3,4,5]`

How does it not generate an error ?

… and I have enough to say on this subject that I thought it would warrant a blog post rather than just a comment reply.

The easiest way to answer this question is to walk through all the possible alternative implementations that can fail when not given enough elements.

#### Solution 0: Output a `Maybe`

The first thing we could try would be to wrap the result in a `Maybe`

, like this:

```
safeTake :: Int -> [a] -> Maybe [a]
0 _ = Just []
safeTake = Nothing
safeTake n [] : xs) = fmap (x :) (safeTake (n - 1) xs) safeTake n (x
```

```
>>> safeTake 3 [0..]
Just [0,1,2]
>>> safeTake 3 []
Nothing
```

The main deficiency with this approach is that it is insufficiently lazy. The result will not produce a single element of the output list until `safeTake`

finishes consuming the required number of elements from the input list.

We can see the difference with the following examples:

```
>>> oops = 1 : 2 : error "Too short"
>>> take 1 (take 3 oops)
1]
[
>>> safeTake 1 =<< safeTake 3 oops
*** Exception: Too short
```

#### Solution 1: Fail with `error`

Another approach would be to create a partial function that fails with an `error`

if we run out of elements, like this:

```
partialTake :: Int -> [a] -> [a]
0 _ = []
partialTake : xs) = x : partialTake (n - 1) xs partialTake n (x
```

```
>>> partialTake 3 [0..]
0,1,2]
[
>>> partialTake 3 []
*Main> partialTake 3 []
*** Exception: Test.hs:(7,1)-(8,51): Non-exhaustive patterns in function partialTake
>>> partialTake 1 (partialTake 3 oops)
1] [
```

Partial functions like these are undesirable, though, so we won’t go with that solution.

#### Solution 2: Use a custom list-like type

Okay, but what if we could store a value at the end of the list indicating whether or not the `take`

succeeded. One way we could do that would be to define an auxiliary type similar to a list, like this:

```
{-# LANGUAGE DeriveFoldable #-}
data ListAnd r a = Cons a (ListAnd r a) | Nil r deriving (Foldable, Show)
```

… where now the empty (`Nil`

) constructor can store an auxiliary value. We can then use this auxiliary value to indicate to the user whether or not the function succeeded or not:

```
data Result = Sufficient | Insufficient deriving (Show)
takeAnd :: Int -> [a] -> ListAnd Result a
0 _ = Nil Sufficient
takeAnd = Nil Insufficient
takeAnd n [] : xs) = Cons x (takeAnd (n - 1) xs) takeAnd n (x
```

```
>>> takeAnd 3 [0..]
Cons 0 (Cons 1 (Cons 2 (Nil Sufficient)))
>>> takeAnd 3 []
Nil Insufficient
```

Also, the `ListAnd`

type derives `Foldable`

, so we can recover the old behavior by converting the `ListAnd Result a`

type into `[a]`

using `toList`

:

```
>>> import Data.Foldable (toList)
>>> toList (takeAnd 3 [0..])
0,1,2]
[
>>> toList (takeAnd 3 [])
[]
>>> toList (takeAnd 1 (toList (takeAnd 3 oops)))
1] [
```

This is the first total function that has the desired laziness characteristics, but the downside is that the `take`

function now has a much weirder type. Can we solve this only using existing types from `base`

?

#### Solution 3: Return a pair

Well, what if we were to change the type of `take`

to return an pair containing an ordinary list alongside a `Result`

, like this:

```
takeWithResult :: Int -> [a] -> ([a], Result)
0 _ = ( [], Sufficient )
takeWithResult = ( [], Insufficient)
takeWithResult n [] : xs) = (x : ys, result )
takeWithResult n (x where
= takeWithResult (n - 1) xs (ys, result)
```

```
>>> takeWithResult 3 [0..]
0,1,2],Sufficient)
([>>> takeWithResult 3 []
Insufficient) ([],
```

Now we don’t need to add this weird `ListAnd`

type to `base`

, and we can recover the old behavior by post-processing the output using `fst`

:

```
>>> fst (takeWithResult 3 [0..])
0,1,2]
[fst (takeWithResult 3 [])
[]
```

… and this also has the right laziness characteristics:

```
>>> fst (takeWithResult 1 (fst (takeWithResult 3 oops)))
1] [
```

… and we can replace `Result`

with a `Bool`

if want a solution that depends solely on types from `base`

:

```
takeWithResult :: Int -> [a] -> ([a], Bool)
0 _ = ([], True)
takeWithResult = ([], False)
takeWithResult n [] : xs) = (x : ys, result)
takeWithResult n (x where
= takeWithResult (n - 1) xs (ys, result)
```

However, even this solution is not completely satisfactory. There’s nothing that forces the user to check the `Bool`

value before accessing the list, so this is not as safe as, say, the `safeTake`

function which returns a `Maybe`

. The `Bool`

included in the result is more of an informational value rather than a safeguard.

#### Conclusion

So the long-winded answer to the original question is that there are several alternative ways we could implement `take`

that can fail if the input list is too small, but in my view each of them has their own limitations.

This is why I think Haskell’s current `take`

function is probably the least worst of the alternatives, even if it’s not the safest possible implementation.

This is a good explanation. The laziness problem with Maybe never occurred to me. In general, are there ways to "thread" the laziness of list-like types through another type like Maybe? Or is this a fundamental language design limitation?

ReplyDelete