Rotating a list in Haskell with all posibilities

Question

How can I edit the following code to make Haskell show all the possibilities of rotating an input list from the user :

rotate ::  Int -> [a] -> [a]
rotate n text = take (length text) (drop n (cycle text))

I assume that to print all the possibilities we need to drop the first element X times. where X is the length of the list entered.

circle ::  [a] -> [[a]]
circle text = take (length text) (drop (1) (cycle text))

I can't perform the operation where the list is printed X times. Also I have errors while running the above code which states the following: Couldn't match type ‘a’ with ‘[a]’

I wanted the Output to be something like that:

circle "ab"
["ab","ba"]

Possible duplicate of [Get all permutations of a list in Haskell](https://stackoverflow.com/questions/40097116/get-all-permutations-of-a-list-in-haskell) — , Sep 26 '19 at 20:40
What if the string is `"abab"`, should that result in `["abab", "baba"]`, or `["abab", "baba", "abab", "baba"]`? — Willem Van Onsem, Sep 26 '19 at 20:48

score 7 · Answer 1 · answered Sep 26 '19 at 21:02

7

You can avoid any calls to length, as well as the repeated calls to cycle and ever-larger arguments to drop, by instead zipping any otherwise-infinite lists against the finite input list, to trim them to be the size you expect, discarding later elements:

circle xs = let trim ys = zipWith const ys xs
            in trim . map trim . iterate tail . cycle $ xs

*Main> circle "abc"
["abc","bca","cab"]

answered Sep 26 '19 at 21:02

amalloy

89,153
8
140
205

1

Use `tails` instead of `iterate tail`. The former doesn't rely on an infinite argument to produce fully-defined results. – dfeuer Sep 26 '19 at 21:27
@dfeuer I considered this, but I didn't really want to add an import, and the argument is guaranteed to be infinite. – amalloy Sep 26 '19 at 22:04
`iterate (drop 1)`? – dfeuer Sep 26 '19 at 22:17
I'm perfectly happy to use `tali` in cases where the list is locally known to be non-empty and pattern-matching would be inconvenient. Until `tail` is removed from the Prelude, I don't want to use weird stuff like `drop 1` to avoid it in the cases it's perfect for. – amalloy Sep 26 '19 at 22:33

score 0 · Answer 2 · answered Sep 26 '19 at 20:41

0

Seems like you're interested in all permutations of all permutations. It means that you're dealing with a [ [] ] - list of list (recall that "ab" is just ['a', 'b']). Data.List has what you need. Source code. Otherwise, I've completely misunderstood your intention.

answered Sep 26 '19 at 20:41

Zazaeil

3,900
2
14
31

3

Rotations are not the same as permutations. For example given "abc", the rotations are "abc", "bca", and "cab". Note that "bac" isn't in this list, even though it is a valid permutation. – Code-Apprentice Sep 26 '19 at 20:46

score 0 · Answer 3 · answered Sep 26 '19 at 20:44

I would start by reusing the rotate function and apply some recursion:

circle text = text : (circle $ rotate text)

Now this produces an infinite list. If you only want each rotation once, then use take:

circle text = take (length text) $ text : (circle $ rotate text)

This version has the disadvantage of calculating the length of text each time you call circle. Instead, you could use a helper function with a counter that decrements for each recursion:

circle = circle' (length text)
  where circle' 0 _ = []
        circle' n text = text : (circle' (rotate text) (n - 1))

Rotating a list in Haskell with all posibilities

3 Answers3