Get all rotations for a string in haskell

user_11092105 0
Viewed 147

So I'm trying to make a function "rot" which takes a string and returns a list of strings with all possible rotations, e.g rot "abc" returns ["abc", "bca", cab"], seems very simple to do in other languages but I'm a newbie at haskell so I can't think of a way to do it. This is what I have so far:

rot :: [Char] -> [[Char]]
rot word = 
    let
        lst = [tail word ++ [head word]]
    in
        lst
    

main = do
    print(rot "abc")

It returns me "bca" as expected, but I would like a way to find all rotations and store it in a list.

Here's an example in python

def rot(word):
    lst = []
    for i in range(len(word)):
        newWord1 = word[0:i]
        newWord2 = word[i:]
        newWordResult = newWord2 + newWord1
        lst.append(newWordResult)
    return lst
haskell
3 Answers

Well, you can more or less directly translate your Python code. Recursion is customarily used in functional programming instead of iteration, and it's more convenient to count from length word down to zero. Other than that, it's pretty much the same:

rot word =
  let loop 0 lst = lst
      loop i lst =
        let newWord1 = take (i-1) word
            newWord2 = drop (i-1) word
            newWordResult = newWord2 ++ newWord1
        in loop (i-1) (newWordResult : lst)

  in loop (length word) []
user_1802860

One can make use of the tails and inits of a list:

Prelude Data.List> tails "abc"
["abc","bc","c",""]
Prelude Data.List> inits "abc"
["","a","ab","abc"]

we thus can use this with:

import Data.List(inits, tails)

rotated :: [a] -> [[a]]
rotated xs = [x ++ y | (x@(_:_), y) <- zip (tails xs) (inits xs)]

This produces:

Prelude Data.List> rotated "abc"
["abc","bca","cab"]
Prelude Data.List> rotated [1,4,2,5]
[[1,4,2,5],[4,2,5,1],[2,5,1,4],[5,1,4,2]]
Prelude Data.List> rotated [1.0,3.0,0.0,2.0]
[[1.0,3.0,0.0,2.0],[3.0,0.0,2.0,1.0],[0.0,2.0,1.0,3.0],[2.0,1.0,3.0,0.0]]

or as @Iceland_jack says, we can use the ParallelListComp extension to allow iterating over two lists in parallel in list comprehension without the explicit use of zip:

{-# LANGUAGE ParallelListComp #-}

import Data.List(inits, tails)

rotated :: [a] -> [[a]]
rotated xs = [x ++ y | x@(_:_) <- tails xs | y <- inits xs]
user_675790

This is, simply,

rotations xs = map (take n) . take n
                 . tails $ xs ++ xs
   where
   n = length xs

It is customary to avoid length if at all possible, though here it leads to a bit more convoluted code(*) (but more often than not it leads to a simpler, cleaner code that is more true to the true nature of the problem),

rotations2 xs = map (zipWith (\a b -> b) xs) 
                 . zipWith (\a b -> b) xs
                 . tails $ xs ++ xs

Testing, we get

> rotations "abcd"
["abcd","bcda","cdab","dabc"]

> rotations2 "abcd"
["abcd","bcda","cdab","dabc"]

> take 4 . map (take 4) $ rotations2 [1..]
[[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7]]

(*) edit Actually, it probably merits its own name,

takeLength :: [a] -> [b] -> [b]
takeLength  =  zipWith (\a b -> b)

rotations2 xs = map (takeLength xs) 
                 . takeLength xs
                 . tails $ xs ++ xs
user_8498910
Related