CODEWITHSUNDEEP
haskell
P. Castro
P. Castro

Reputation: 43

Get all rotations for a string in haskell

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

Upvotes: 2

Views: 190

Answers (3)

Will Ness
Will Ness

Reputation: 71119

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

Upvotes: 3

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477608

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]

Upvotes: 3

Fyodor Soikin
Fyodor Soikin

Reputation: 80880

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) []

Upvotes: 3

Related Questions