如何避免zipWith自引用场景下的无限循环？（Haskell适配）

问题背景 #

我要为一款依赖自引用与惰性特性、仅通过值而非用户函数实现图灵完备的小众语言，设计一种列表数据结构，让它的zipWith操作在自引用场景下表现更优。之前开发的Atlas版本内置功能过多，现在希望简化并能在Haskell中编译/解释。

标准zipWith的逻辑是检查任意一个列表是否为空，为空则返回空列表，但当zipWith的结果依赖自身输出时，会直接陷入无限循环。我需要能检测这类场景，默认列表不会为空。

以下是用DList实现的示例代码，本应对[5,6,7]求和，但无法正常运行：

import Data.DList
import Data.List (uncons)

zipDL :: (a->b->c) -> DList a -> DList b -> DList c
zipDL f a b = fromList $ zipL f (toList a) (toList b)

zipL :: (a->b->c) -> [a] -> [b] -> [c]
zipL _ [] _ = []
zipL _ _ [] = []
zipL f ~(a:as) ~(b:bs) = f a b : zipL f as bs

a = fromList [5,6,7]

main=print $ dh where
   d = zipDL (+) a $ snoc (fromList dt) 0
   ~(Just (dh,dt)) = uncons $ toList d

问题本质分析 #

从列表大小的维度看：

zip a b的大小 = min( size a, size b )

在上述示例中，size d = min( size a, size d-1+1 )，这个等式存在多个解：size d为0、1直到size a的值都满足等式，导致结果未定义。我需要让size d固定等于size a。

尝试过的解决方案 #

临时移除空列表检查 #

移除zipL _ _ [] = []可以修复示例问题，因为此时默认结果列表非空，符合实际场景，但这不是通用方案——我们无法总是假定第二个列表存在自引用。

Maybe包装的无限列表方案 #

我把所有列表用Maybe包装，用Nothing标记列表结束，在zipWith的二元函数里处理Maybe值，移除zip中的空列表检查，将所有列表视为无限列表。为让求和示例正常运行，用mapOr操作替换snoc，把所有Nothing值替换为指定值。

代码实现：

import Data.Maybe

data L a = L (Maybe a) (L a)

nil :: L a
nil = L Nothing nil

fromL :: [a] -> L a
fromL [] = nil
fromL (x:xs) = L (Just x) (fromL xs)

binOpMaybe :: (a->b->c) -> Maybe a -> Maybe b -> Maybe c
binOpMaybe f Nothing _ = Nothing
binOpMaybe f _ Nothing = Nothing
binOpMaybe f (Just a) (Just b) = Just (f a b)

zip2W :: (a->b->c) -> L a -> L b -> L c
zip2W f ~(L a as) ~(L b bs) = L (binOpMaybe f a b) (zip2W f as bs)

unconsL :: L a -> (Maybe a, Maybe (L a))
unconsL ~(L a as) = (a, Just as)

mapOr :: a -> L a -> L a
mapOr v ~(L a as) = L (Just $ fromMaybe v a) $ mapOr v as

main=print $ h
   where
   a = fromL [4,5,6]
   b = zip2W (+) a (mapOr 0 (fromJust t))
   (h,t) = unconsL $ b

这个方案的缺点是mapOr远不如++直观——原本语言完全可以基于++、uncons和(:[])构建，会简洁很多。

Ruby中的错误捕获方案 #

我在当前Ruby实现中尝试过另一种方法：当值依赖自身时抛出错误，在空列表检测时捕获该错误。这种方法能在这类场景生效，但非常不规范且不完全可靠，而且我认为Haskell里无法实现，因为Haskell无法检测自依赖。

后续思考 #

把问题归类为最大不动点问题后，我发现这类问题没有高效通用解决方案。对我的需求而言，能正确处理部分场景仍有价值，但将其作为编程语言的基础规则并不合适。

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