Haskell中如何实现尾递归的字符串拆分？

我正在研究将字符串s按字符c拆分的问题，这个需求可以用break (c ==) s来实现。Haskell标准库中break (c ==)的大致实现如下：

br []      = ([],[])
br s@(h:t) = if (c == h)
             then ([],s)
             else let (h',t') = br t in (h:h',t')

假设我们会立即获取返回值的第二个元素以触发惰性求值，此时递归调用br t会把h存储在调用栈中，但从算法逻辑来看这其实没必要。下面是带可变性的伪代码实现（&表示传引用，列表采用LISP式的配对结构）：

br(c,s) = 
  allocate res_head,res_rest
  iter(c,s,&res_head,&res_rest)
  return (res_head,res_rest)
iter(c,s,&res_head,&res_rest) =
  case s of
    []   -> set res_head = res_rest = []         -- 终止
    c:ss -> set res_head = [], res_rest = s      -- 终止
    x:ss -> allocate new_pair
            set res_head = new_pair, new_pair.head = x
            iter(c,ss,&new_pair.tail,&res_rest)  -- 尾调用/跳转

不管GHC能不能自动优化，我想在Haskell里写出显式的尾递归实现，该怎么做？

实现方案 #

在纯函数式的Haskell中，我们无法直接使用可变引用，但可以通过累加器模拟伪代码里的“引用传递”逻辑，写出显式尾递归的实现。核心思路是用累加器逐步构建不匹配字符的列表（反向存储，最后反转修正顺序），让递归调用始终作为函数的最后操作：

breakTail :: Eq a => a -> [a] -> ([a], [a])
breakTail c s = go [] s
  where
    -- 尾递归辅助函数：累加器（已遍历的非匹配字符，反向） -> 剩余列表 -> 结果
    go acc [] = (reverse acc, [])
    go acc (x:xs)
      | x == c    = (reverse acc, x:xs)
      | otherwise = go (x:acc) xs

逻辑说明 #

• go是标准的尾递归函数：每次递归调用都是函数的最终操作，GHC可直接将其优化为循环，不会产生栈堆积问题。
• 累加器acc存储的是已遍历的非匹配字符，但因为每次将新字符加到头部，所以最后需要用reverse反转得到正确顺序。
• 触发终止条件时（遇到匹配字符或遍历结束），直接返回反转后的累加器作为前半部分，剩余列表作为后半部分，和标准break行为完全一致。

示例验证 #

调用breakTail 'a' "xyzabc"的执行流程：

1. go [] "xyzabc" → x≠a → go ['x'] "yzabc"
2. go ['x'] "yzabc" → y≠a → go ['y','x'] "zabc"
3. go ['y','x'] "zabc" → z≠a → go ['z','y','x'] "abc"
4. go ['z','y','x'] "abc" → a==a → 返回(reverse ['z','y','x'], "abc") → ("xyz", "abc")

若想避免reverse，也可以通过构建“延迟反转”的链表优化，但上述实现已经满足显式尾递归的要求，且逻辑清晰易懂。

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