https://wiki.haskell.org/api.php?action=feedcontributions&user=Anphung&feedformat=atomHaskellWiki - User contributions [en]2022-08-14T15:31:36ZUser contributionsMediaWiki 1.31.7https://wiki.haskell.org/index.php?title=99_questions/Solutions/19&diff=6441599 questions/Solutions/192021-05-23T20:35:02Z<p>Anphung: Remove solution that doesn't work</p>
<hr />
<div>(**) Rotate a list N places to the left.<br />
<br />
Hint: Use the predefined functions length and (++).<br />
<br />
<haskell><br />
rotate [] _ = []<br />
rotate xs 0 = xs<br />
rotate (x:xs) (n+1) = rotate (xs ++ [x]) n<br />
rotate xs n = rotate xs (length xs + n)<br />
</haskell><br />
<br />
(Note that this solution uses [http://en.wikibooks.org/wiki/Haskell/Pattern_matching#n.2Bk_patterns n+k-patterns] which are [http://www.haskell.org/onlinereport/haskell2010/haskellli2.html#x3-5000 removed] from Haskell 2010.) <br />
<br />
There are two separate cases:<br />
* If n > 0, move the first element to the end of the list n times.<br />
* If n < 0, convert the problem to the equivalent problem for n > 0 by adding the list's length to n.<br />
<br />
or using cycle:<br />
<haskell><br />
rotate xs n = take len . drop (n `mod` len) . cycle $ xs<br />
where len = length xs<br />
</haskell><br />
<br />
or using list comprehension (only works for sequential increasing elements):<br />
<haskell><br />
rotate :: (Enum a) => [a] -> Int -> [a]<br />
rotate xs n = [(f n) .. last xs] ++ [head xs .. (f (n-1))]<br />
where f k = xs !! (k `mod` length xs)<br />
</haskell><br />
<br />
or without mod:<br />
<haskell><br />
rotate xs n = take (length xs) $ drop (length xs + n) $ cycle xs<br />
</haskell><br />
<br />
or<br />
<br />
<haskell><br />
rotate xs n = if n >= 0 then<br />
drop n xs ++ take n xs<br />
else let l = ((length xs) + n) in<br />
drop l xs ++ take l xs<br />
</haskell><br />
<br />
or<br />
<br />
<haskell><br />
rotate xs n | n >= 0 = drop n xs ++ take n xs<br />
| n < 0 = drop len xs ++ take len xs<br />
where len = n+length xs<br />
</haskell><br />
<br />
or calculate the position at first:<br />
<br />
<haskell><br />
rotate xs n = let i = if n < 0 then length xs + n else n<br />
in drop i xs ++ take i xs<br />
</haskell><br />
<br />
or<br />
<br />
<haskell><br />
rotate xs n = drop nn xs ++ take nn xs<br />
where <br />
nn = n `mod` length xs<br />
</haskell><br />
<br />
Using a simple splitAt trick<br />
<haskell><br />
rotate xs n<br />
| n < 0 = rotate xs (n+len)<br />
| n > len = rotate xs (n-len)<br />
| otherwise = let (f,s) = splitAt n xs in s ++ f<br />
where len = length xs<br />
</haskell><br />
<br />
A much simpler solution without using <hask>length</hask> that is very similar to the first solution:<br />
<haskell><br />
rotate :: [a] -> Int -> [a]<br />
rotate [] _ = []<br />
rotate x 0 = x<br />
rotate x y<br />
| y > 0 = rotate (tail x ++ [head x]) (y-1)<br />
| otherwise = rotate (last x : init x) (y+1)<br />
</haskell><br />
<br />
Here's another solution without using length. If the order of the arguments is reversed so that the integer comes before the list, then it is possible to define rotation by n as rotation by (n-1) followed by rotation by 1 recursively (with suitable modifications to support negative rotations). This leads to the following solution:<br />
<haskell><br />
rotate :: [a] -> Int -> [a]<br />
rotate xs n = rot n xs<br />
where rot 0 = id<br />
rot 1 = \xs -> case xs of [] -> []; xs -> tail xs ++ [head xs]<br />
rot (-1) = \xs -> case xs of [] -> []; xs -> (last xs):init xs<br />
rot n<br />
| n > 0 = (rot (n-1)).(rot 1)<br />
| n < 0 = (rot (n+1)).(rot (-1))<br />
</haskell><br />
<br />
[[Category:Programming exercise spoilers]]</div>Anphung