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"
[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])
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.
I think you want something like this:
rotate :: Int -> [a] -> [a]
rotate 0 x = x
rotate times (x:xs) = rotate (times - 1) (xs ++ [x])
