CODEWITHSUNDEEP
haskell
Tony Chamberlain
Tony Chamberlain

Reputation: 171

Syntax for List Patterns in Function Declaration

I'm learning haskell and have been writing various fairly trivial functions to get a handle on the language. I wrote this function:

doubleOneOrTail :: [t]->[t]
doubleOneOrTail [x] = [x,x]
doubleOneOrTail (x:xs)  = xs

Which does exactly what is says. Doubles the list of 1 element, or returns the tail of a list of multiple elements. This generic syntax will work for a list of single elements or list of lists, etc. I can rewrite this function to the following:

doubleOneOrTail :: [[t]]->[[t]]
doubleOneOrTail [[x]] = [[x,x]]
doubleOneOrTail (x:xs)  = xs

This will throw an error if I type the following:

doubleOneOrTail [1,2,3]

but it does accept this:

doubleOneOrTail [[[[1,2,3],[2]]]]

Treats it as a list with a single element (that element being a list of lists) and doubles it.

Clearly the pattern [a]->[a] isn't matching a list of single elements but in some way matching any order of lists. Whlie [[a]]->[[a]] is also matching multiple orders of lists (though not lists of just single elements). If anyone could explain how this is working it would be greatly appreciated.

A secondary question is it possible (or even desirable) to have a function declaration that specifically takes a particular order of a list. Say only lists of lists?

Upvotes: 1

Views: 76

Answers (2)

Sergey Romanovsky
Sergey Romanovsky

Reputation: 4554

Little addition to @amalloy answer. Most probably you'll be fine with Enum class constraint:

doupbleOneOrTrail :: (Enum t) => [t] -> [t]

So your function accepts list of chars, numbers, booleans, etc

λ: doubleOneOrTail "foo"
"oo"
λ: doubleOneOrTail [False]
[False,False]

Upvotes: 0

amalloy
amalloy

Reputation: 91982

It sounds like you have a pretty good understanding of what's surprising you here: [a] is a list of any type of thing at all, including a list of lists. You can work out by hand what the type inferencer does automatically. Suppose that, using your first definition, we write:

let xs = [[[1,2], [3,4]], [[5]]]
in doubleOneOrTail xs

At this point GHC has to make sure the types match up for us.

xs :: [[[Integer]]] -- really could be any Num type, but assume Integer

Now since we're calling doubleOneOrTail with an [[[Integer]]] as argument, GHC must unify the types [a] and [[[Integer]]], which means finding some concrete type to substitute for a that makes the two types match up. There is only one correct answer:

[a] ~ [[[Integer]]]
a ~ [[Integer]]

Therefore, we are doubling or tailing a list of things, where each thing is a list of list of numbers. And since the types do indeed unify, GHC gives the all-clear, the function call compiles, and as a result we get [[[5]]].

As to your second question, whether you could or should restrict to a particular depth of lists: usually you should not. This kind of function is called parametrically polymorphic, meaning it works for any kind of a at all, no matter what it is; this is a useful property that it's good to preserve when possible. If your function doesn't need to look at values of its a type in order to perform correctly, it should allow them to be of any type.

Suppose that you still wanted to restrict its type? I don't know of a way to restrict it to depth-one lists without also adding some other incidental restriction. For example, you could say that it must be a list of numbers (and hope that nobody defines a Num instance for lists!):

doubleOneOrTail :: Num a => [a] -> [a]

Or you could limit it to a very specific type, such as [Int]. This would guarantee it can only ever be called with that type.

doubleOneOrTail :: [Int] -> [Int]

But as discussed above, all of these approaches unnecessarily restrict the type of your function. Better to define it as generally as possible, and find some other way to satisfy whatever other concerns make you want to restrict its type.

Upvotes: 3

Related Questions