Haskell 移位表

Question

我想将列表向左移动 n 个元素。如果我想将顺序从 (x:xs) 更改为 (xs:x)，为什么会出现错误？

shift n list@(x:xs)
    | n == 0 = list
    | otherwise = shift (n-1) (xs:x) -- (xs:x) error

Occurs check: cannot construct the infinite type: a ~ [a]

我不知道如何解释这个错误。也许你们中有人可以帮助我。非常感谢。

EDIT: As it was already mentioned, the correct term to use is rotate and not shift

Answer 1

Why do I get an error if I want to change the order from (x:xs) to (xs:x)?

因为类型不匹配。 (:) 的类型是 (:)::a -> [a] -> [a]。因此，它需要一个元素x(类型a)和一个包含其余元素的列表(类型[a])。您不能仅以相反的方式使用 (:)。

您可以使用 (++) :: [a] -> [a] -> [a]将两个列表连接在一起。因此，我们可以通过从列表中删除 n 元素并将其与列表的前 n 元素连接到此来向左旋转。

<b>rotateL</b> :: Int -> [a] -> [a]
rotateL 0 list = list
rotateL n list | n < 0 = error "Negative index"
               | otherwise = <b>drop n list ++ take n list</b>

或者我们可以，比如 @YannVernier说，使用 splitAt :: Int -> [a] -> ([a], [a]) :

rotateL :: Int -> [a] -> [a]
rotateL 0 list = list
rotateL n list | n < 0 = error "Negative index"
               | otherwise = <b>lb ++ la</b>
    where (la, lb) = splitAt n list

或者不提及 list 参数:

rotateL :: Int -> [a] -> [a]
rotateL 0 = id
rotateL n | n < 0 = error "Negative index"
          | otherwise= <b>uncurry (flip (++)) . splitAt n</b>

Note: based on how your attempt, I think you actually want to rotate the list to the left, not shift it, since that would mean that you simply drop the first n elements, and fill it perhaps with some extra value.

Note: in case n is larger than the length of the list, then the rotateL will act as an identity function. That might not be the desired behavior. I leave it as an exercise to fix this edge-case.