Haskell新手求助：实现按指定次数移动列表元素的shift函数

Hey there! Let's walk through building this shift function step by step—since you're new to Haskell, I'll keep explanations straightforward and avoid unnecessary jargon.

First, let's recap the requirements to make sure we're aligned:

• Function signature: shift :: Eq a => a -> [a] -> Int -> [a]
• Precondition: The element x definitely exists in the input list
• Behavior rules:
  • If n == 0: Remove the first occurrence of x
  • If n < 0: Shift the first occurrence of x left by abs(n) positions (stop at the list head if we can't shift further)
  • If n > 0: Shift the first occurrence of x right by n positions (stop at the list tail if we can't shift further)

Step 1: Split the List at the First x #

First, we need a helper function to split the input list into two parts: all elements before the first x, and all elements after the first x. We can use Haskell's built-in break function here—since we know x is in the list, we don't have to handle edge cases where x is missing.

splitOnce :: Eq a => a -> [a] -> ([a], [a])
splitOnce x xs = let (before, _:after) = break (==x) xs in (before, after)

• break (==x) xs splits the list into the longest prefix with no x, and the rest of the list (which starts with x)
• We pattern match on _:after to discard the x itself, leaving us with before (elements before x) and after (elements after x)

Step 2: Core shift Logic #

Now we can use splitOnce to handle each case for n:

shift :: Eq a => a -> [a] -> Int -> [a]
shift x xs n = let (before, after) = splitOnce x xs
                   lenBefore = length before
                   lenAfter = length after
               in case compare n 0 of
                   EQ -> before ++ after  -- n=0: remove first x
                   LT -> let shiftLeft = min (abs n) lenBefore
                             (keepBefore, moveToAfter) = splitAt (lenBefore - shiftLeft) before
                         in keepBefore ++ [x] ++ moveToAfter ++ after
                   GT -> let shiftRight = min n lenAfter
                             (moveToBefore, keepAfter) = splitAt shiftRight after
                         in before ++ moveToBefore ++ [x] ++ keepAfter

Let's Break Down Each Case: #

1. When n == 0:

   • We just concatenate before and after, which removes the first x entirely (since we split it out earlier)

2. When n < 0 (Shift Left):

   • shiftLeft calculates how many valid left shifts we can do—we can't shift left more times than there are elements before x, so we take the minimum of abs(n) and the length of before
   • splitAt (lenBefore - shiftLeft) before splits before into elements that stay before x (keepBefore) and elements that move to after x (moveToAfter)
   • We reassemble the list: keepBefore → x → moveToAfter → after

3. When n > 0 (Shift Right):

   • shiftRight calculates how many valid right shifts we can do—we can't shift right more times than there are elements after x, so we take the minimum of n and the length of after
   • splitAt shiftRight after splits after into elements that move to before x (moveToBefore) and elements that stay after x (keepAfter)
   • We reassemble the list: before → moveToBefore → x → keepAfter

Example Usage #

Let's test this with some concrete examples to verify it works:

• shift 'x' ['a','b','x','c','d'] 0 → ['a','b','c','d'] (removes x)
• shift 'x' ['a','b','x','c','d'] (-1) → ['a','x','b','c','d'] (shifts left 1)
• shift 'x' ['a','b','x','c','d'] (-2) → ['x','a','b','c','d'] (shifts left 2, hits the list head)
• shift 'x' ['a','b','x','c','d'] 1 → ['a','b','c','x','d'] (shifts right 1)
• shift 'x' ['a','b','x','c','d'] 3 → ['a','b','c','d','x'] (shifts right 2, hits the list tail—only 2 elements exist after x)

内容的提问来源于stack exchange，提问作者White_Sirilo