Rotate function in Haskell

2
votes

I want to write a function in Haskell that rotates the list given as the second argument by the number of positions indicated by the first argument. Using pattern matching, implement a recursive function

I have written the following function:

rotate :: Int -> [a] -> [a]
rotate 0 [y]= [y]
rotate x [y]= rotate((x-1) [tail [y] ++ head [y]])

but this function always produces a error. Is there any way to solve it? The function should do the following when it runs:

rotate 1 "abcdef"
"bcdefa"
3
haskellrecursionpattern-matching
Please do not vandalize your posts. If you believe your question is not useful or is no longer useful, it should be deleted instead of editing out all of the data that actually makes it a question. By posting on the Stack Exchange network, you've granted a non-revocable right for SE to distribute that content (under the CC BY-SA 3.0 license). By SE policy, any vandalism will be reverted. – Filnor
You can't easily delete a question which has upvoted answers, though. – tripleee

3 Answers

6
votes

[y] does not mean "let y be a list". It means "this argument is a list containing one element called y". You have the right structure, but you don't need the brackets around the y.

rotate :: Int -> [a] -> [a]
rotate 0 y = y
rotate x y = rotate (x-1) (tail y ++ [head y])
1
votes

I think you want something like this:

rotate :: Int -> [a] -> [a]
rotate 0 x = x
rotate times (x:xs) = rotate (times - 1) (xs ++ [x])
1
votes

TL&DR

rotate :: Int -> [a] -> [a]
rotate = drop <> take

In Haskell the most concise but also a curious way to rotate a list could be using the Semigroup type class instance of the function type (a -> b). Lets check the relevant part of the instance.

instance Semigroup b => Semigroup (a -> b) where
        f <> g = \x -> f x <> g x

First things first, <> is in fact the inline version of the mappend function from the Monoid type class.

Then we see, the Semigroup b => constraint in the type signature states that the return type b should also be a member of Semigroup type class. Since we use drop :: Int -> [a] -> [a] and take :: Int -> [a] -> [a] we can quickly notice that b is in fact another function with type signature [a] -> [a] so it is a member of Semigroup type class if and only if it's b, which happens to be [a] is also a member of the Semigroup type class and it is.

instance Semigroup [a] where
        (<>) = (++)

So everything holds so far but how does it work?

We can deduce from the type signatures as follows;

  • (drop :: Int -> ([a] -> [a])) <> (take :: Int -> ([a] -> [a])) is
  • \n -> (drop n :: [a] -> [a]) <> (take n :: [a] -> [a]) which is
  • \n -> \xs -> (drop n xs :: [a]) <> (take n xs :: [a]) which is
  • \n -> \xs -> (drop n xs) ++ (take n xs)

This is basically better than the answers using recursive ++ operator to add the head as a singleton list to the end of the tail since it yields an O(n^2) time complexity.