0

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)
8
  • But it doesn't help me specifically for my example. I still don't know the answer. Commented Nov 13, 2017 at 3:01
  • But your question is the same as the linked question. Is there some part of the answer that you don't understand? Commented Nov 13, 2017 at 3:02
  • So I should do it with iterate? Commented Nov 13, 2017 at 3:17
  • No, you should not do it with iterate, or anything of the like. Doing the same thing n times is is absolutely the wrong way to rotate a list! Commented Nov 13, 2017 at 3:25
  • 2
    Haskell has no while operator. Commented Nov 13, 2017 at 8:47

2 Answers 2

1

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.

Sign up to request clarification or add additional context in comments.

7 Comments

If I rotate it for example seven times it would be the same as I would rotate it 1 time with 6 elements.So basically I just divide the amount of rotations I do by n-elements and my remainder will be the total amount of rotations. For example if I want to rotate the list 23 times with 6 elements, then I do 23/6= 3 mod 5 -> So 5 rotations. But I still don't know how to make it recursive, the efficiency is not so important for me.
@Paddy369, what do you mean, "make it recursive"?
I mean that it won't rotate just once, but rather 3, or 4 times.
My problem I have that I don't know what to write in Haskell so the rotation won't be only once. Currently your rotateLeft1 function only rotates once, so my question is, how do I write the rotateLeft function.
@Paddy369, I outlined the procedure I suggest for writing rotateLeft, which does not involve any calls to rotateLeft1. What specific aspect do you find hard to understand?
|
0

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.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.