CODEWITHSUNDEEP
haskell
Paddy369
Paddy369

Reputation: 1

How can I make my simple Haskell function recursive?

This is my function:

rotatebyone :: [Int] -> [Int]
rotatebyone [] = []
rotatebyone (x:xs) = ((tail (x:xs)) ++ (take 1 (x:xs)))

rotatebyn :: Int -> [Int] -> [Int]
rotatebyn n [] = []
rotatebyn 1 (x:xs) = rotatebyone (x:xs) 
rotatebyn 2 (x:xs) = (rotatebyone (rotatebyone (x:xs)))

I want my function to repeat itself for n-times. I guess you do this with guardians or the "while" operator, but I don't know quite how. The goal is to rotate elements of a integer-list n-times.

This was my failed approach:

rota :: Int -> [Int] -> [Int]
rota n (x:xs) = rotatebyone (x:xs)
                where
                rota n
                    | n > 1 = rota (n - 1)
                    | otherwise = rotatebyone (x:xs)

Upvotes: 0

Views: 131

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477607

Let us first clean up the rotatebyone function:

rotatebyone :: [Int] -> [Int]
rotatebyone [] = []
rotatebyone (x:xs) = ((tail (x:xs)) ++ (take 1 (x:xs)))

Here you call tail on (x:xs) but that is quite weird, since we already have a tail: xs. So we can replace tail (x:xs) with xs.

The same holds for take 1 (x:xs). This will construct a list with the head of the list, so [x]. So we can clean up the code to:

rotatebyone :: [Int] -> [Int]
rotatebyone [] = []
rotatebyone (x:xs) = xs ++ [x]

Furthermore your function only works on lists of type Int (it has signature [Int] -> [Int]). We can however rotate lists by one regardless the type of elements these lists hold, so we can write it as:

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

Now we can look for a way to rotate n times with:

rotatebyn :: Int ->[a] -> [a]
rotatebyn ...

In case we wish to rotate over zero places, then the list remains the same, so as a base case we can write:

rotatebyn 0 l = l

and in case we want to rotate over one or more places, we can rotate over one place by the rotatebyone function, and then rotate this result another n-1 times:

rotatebyn n l = rotatebyn (n-1) (rotateone n)

or these together:

rotatebyn :: Int ->[a] -> [a]
rotatebyn 0 l = l
rotatebyn n l = rotatebyn (n-1) (rotateone n)

But the above is, like @dfeuer says not efficient: it takes O(n) time to rotate a list, if we need to do this k times, the time complexity is thus O(n k).

Note furthermore that the above function only works in case n is greater than or equal to zero.

Upvotes: 0

dfeuer
dfeuer

Reputation: 48621

You shouldn't rotate multiple places by rotating once and doing that repeatedly. Let's look at a slightly cleaner version of your single rotation to see why:

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

The problem is that p ++ q takes time linear in the length of p. You're doing that once for each rotation step, which wastes a lot of time. Let's look at it differently, with an example.

rotateLeft 3 [1,2,3,4,5,6,7,8]
-- split the list
([1,2,3], [4,5,6,7,8])
-- swap the pieces
([4,5,6,7,8], [1,2,3])
-- Append
[4,5,6,7,8,1,2,3]

There's one tricky bit left: what if I rotate a list by a number greater than its length? I'll let you give that a go yourself.

Upvotes: 1

Related Questions