Does there exist something like (xs:x)

Question

I'm new to Haskell. I know I can create a reverse function by doing this:

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = (Main.reverse xs) ++ [x]

Is there such a thing as (xs:x) (a list concatenated with an element, i.e. x is the last element in the list) so that I put the last list element at the front of the list?

rotate :: [a] -> [a]
rotate [] = []
rotate (xs:x) = [x] ++ xs

I get these errors when I try to compile a program containing this function:

Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `rotate'

Answer 1

I'm also new to Haskell, so my answer is not authoritative. Anyway, I would do it using last and init:

Prelude> last [1..10] : init [1..10]
[10,1,2,3,4,5,6,7,8,9]

or

Prelude> [ last [1..10] ] ++ init [1..10]
[10,1,2,3,4,5,6,7,8,9]

Answer 2

The short answer is: this is not possible with pattern matching, you have to use a function.

The long answer is: it's not in standard Haskell, but it is if you are willing to use an extension called View Patterns, and also if you have no problem with your pattern matching eventually taking longer than constant time.

The reason is that pattern matching is based on how the structure is constructed in the first place. A list is an abstract type, which have the following structure:

data List a = Empty | Cons a (List a)
           deriving (Show) -- this is just so you can print the List 

When you declare a type like that you generate three objects: a type constructor List, and two data constructors: Empty and Cons. The type constructor takes types and turns them into other types, i.e., List takes a type a and creates another type List a. The data constructor works like a function that returns something of type List a. In this case you have:

Empty :: List a

representing an empty list and

Cons :: a -> List a -> List a

which takes a value of type a and a list and appends the value to the head of the list, returning another list. So you can build your lists like this:

empty = Empty         -- similar to []
list1 = Cons 1 Empty  -- similar to 1:[] = [1]
list2 = Cons 2 list1  -- similar to 2:(1:[]) = 2:[1] = [2,1]

This is more or less how lists work, but in the place of Empty you have [] and in the place of Cons you have (:). When you type something like [1,2,3] this is just syntactic sugar for 1:2:3:[] or Cons 1 (Cons 2 (Cons 3 Empty)).

When you do pattern matching, you are "de-constructing" the type. Having knowledge of how the type is structured allows you to uniquely disassemble it. Consider the function:

head :: List a -> a
head (Empty) = error " the empty list have no head"
head (Cons x xs) = x

What happens on the type matching is that the data constructor is matched to some structure you give. If it matches Empty, than you have an empty list. If if matches Const x xs then x must have type a and must be the head of the list and xs must have type List a and be the tail of the list, cause that's the type of the data constructor:

Cons  :: a -> List a -> List a

If Cons x xs is of type List a than x must be a and xs must be List a. The same is true for (x:xs). If you look to the type of (:) in GHCi:

> :t (:) 
 (:) :: a -> [a] -> [a]

So, if (x:xs) is of type [a], x must be a and xs must be [a] . The error message you get when you try to do (xs:x) and then treat xs like a list, is exactly because of this. By your use of (:) the compiler infers that xs have type a, and by your use of ++, it infers that xs must be [a]. Then it freaks out cause there's no finite type a for which a = [a] - this is what he's trying to tell you with that error message.

If you need to disassemble the structure in other ways that don't match the way the data constructor builds the structure, than you have to write your own function. There are two functions in the standard library that do what you want: last returns the last element of a list, and init returns all-but-the-last elements of the list.

But note that pattern matching happens in constant time. To find out the head and the tail of a list, it doesn't matter how long the list is, you just have to look to the outermost data constructor. Finding the last element is O(N): you have to dig until you find the innermost Cons or the innermost (:), and this requires you to "peel" the structure N times, where N is the size of the list.

If you frequently have to look for the last element in long lists, you might consider if using a list is a good idea after all. You can go after Data.Sequence (constant time access to first and last elements), Data.Map (log(N) time access to any element if you know its key), Data.Array (constant time access to an element if you know its index), Data.Vector or other data structures that match your needs better than lists.

Ok. That was the short answer (:P). The long one you'll have to lookup a bit by yourself, but here's an intro.

You can have this working with a syntax very close to pattern matching by using view patterns. View Patterns are an extension that you can use by having this as the first line of your code:

{-# Language ViewPatterns #-}

The instructions of how to use it are here: http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns

With view patterns you could do something like:

view :: [a] -> (a, [a])
view xs = (last xs, init xs)

someFunction :: [a] -> ...
someFunction (view -> (x,xs)) = ...

than x and xs will be bound to the last and the init of the list you provide to someFunction. Syntactically it feels like pattern matching, but it is really just applying last and init to the given list.

Answer 3

If you're willing to use something different from plain lists, you could have a look at the Seq type in the containers package, as documented here. This has O(1) cons (element at the front) and snoc (element at the back), and allows pattern matching the element from the front and the back, through use of Views.