CODEWITHSUNDEEP
haskellrecursion
Habebit
Habebit

Reputation: 975

Haskell shift list

I want to shift a list by n elements to the left. Why do I get an error if I want to change the order from (x:xs) to (xs:x)?

shift n list@(x:xs)
    | n == 0 = list
    | otherwise = shift (n-1) (xs:x) -- (xs:x) error

Occurs check: cannot construct the infinite type: a ~ [a]

I don't know how to interpret this error. Maybe someone of you can help me. Thank you very much.

EDIT: As it was already mentioned, the correct term to use is rotate and not shift

Upvotes: 2

Views: 2400

Answers (2)

Yann Vernier
Yann Vernier

Reputation: 15887

It's not the names that define the types, but the positions in a function call, or type declarations. If we check the type of :, we see that the second argument is a list:

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

So pattern matching on this constructor will always give you the head and tail, not the init and last. Thus, using both x:xs and xs:x, you've declared that a and [a] are the same type, and the compiler balks. You could perform the append using e.g. xs ++ [x].

Data.Sequence has a type that does support both head and last patterns in the operators :<| and |>:.

In general, (singly linked) lists only make the head element efficiently accessible; operations like appending or even checking lengths are costly. When all you need is a stream or stack, they're great, but a long distance reordering operation like the rotation is better handled by a rope or circular buffer type. Either is available in Haskell, in e.g. container's Seq or ring-buffer's RingBuffer. Data.ByteString.Lazy and Data.Text.Lazy are also rope types.

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477170

Why do I get an error if I want to change the order from (x:xs) to (xs:x)?

Because the types do not match. The type of (:) is (:) :: a -> [a] -> [a]. It thus expects an element x (type a) and a list with the rest of the elements (type [a]). You can not just use (:) in the opposite way.

You can use the (++) :: [a] -> [a] -> [a] to concatenate two lists together. We can thus rotate to the left by dropping n elements from the list and concatenating this with the first n elements of the list to this.

rotateL :: Int -> [a] -> [a]
rotateL 0 list = list
rotateL n list | n < 0 = error "Negative index"
               | otherwise = drop n list ++ take n list

or we can, like @YannVernier says, use splitAt :: Int -> [a] -> ([a], [a]):

rotateL :: Int -> [a] -> [a]
rotateL 0 list = list
rotateL n list | n < 0 = error "Negative index"
               | otherwise = lb ++ la
    where (la, lb) = splitAt n list

or without mentioning the list parameter:

rotateL :: Int -> [a] -> [a]
rotateL 0 = id
rotateL n | n < 0 = error "Negative index"
          | otherwise= uncurry (flip (++)) . splitAt n

Note: based on how your attempt, I think you actually want to rotate the list to the left, not shift it, since that would mean that you simply drop the first n elements, and fill it perhaps with some extra value.

 

Note: in case n is larger than the length of the list, then the rotateL will act as an identity function. That might not be the desired behavior. I leave it as an exercise to fix this edge-case.

Upvotes: 6

Related Questions