1

所以我正在尝试制作一个函数“rot”，它接受一个字符串并返回一个具有所有可能旋转的字符串列表，例如 rot “abc”返回 [“abc”，“bca”，cab”]，看起来很简单用其他语言做，但我是haskell的新手，所以我想不出办法。这就是我到目前为止所拥有的：

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

main = do
    print(rot "abc")

它按预期返回“bca”，但我想要一种查找所有旋转并将其存储在列表中的方法。

这是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
4

3 回答 3

3

好吧，您可以或多或少地直接翻译您的 Python 代码。在函数式编程中习惯使用递归而不是迭代，从length word下到零倒数更方便。除此之外，它几乎相同：

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) []
于 2020-10-28T13:42:02.867 回答
3

可以使用列表的tailsand inits：

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

因此，我们可以将其用于：

import Data.List(inits, tails)

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

这会产生：

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

或者正如@Iceland_jack 所说，我们可以使用ParallelListComp扩展来允许在列表理解中并行迭代两个列表，而无需显式使用zip：

{-# LANGUAGE ParallelListComp #-}

import Data.List(inits, tails)

rotated :: [a] -> [[a]]
rotated xs = [x ++ y | x@(_:_) <- tails xs | y <- inits xs]
于 2020-10-28T16:08:43.827 回答
3

这很简单，

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

如果可能的话，通常会避免length，尽管在这里它会导致更复杂的代码（ * ）（但通常会导致更简单、更清晰的代码，更符合问题的真实性质），

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

测试，我们得到

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

( * ) 编辑实际上，它可能值得拥有自己的名字，

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

rotations2 xs = map (takeLength xs) 
                 . takeLength xs
                 . tails $ xs ++ xs
于 2020-10-28T17:17:09.403 回答