是(map f)== concatMap(map f.(:[]))？

Question

我为类定义了流函数(SF)的left/ right方法,ArrowChoice如下所示: newtype SF a b = SF { runSF :: [a] -> [b] }

instance ArrowChoice SF where
  left (SF f) =
   SF $ map (either (\x -> Left . head $ f [x]) Right)
  right (SF f) =
   SF $ map (either Left (\x -> Right . head $ f [x]))

ghci中的一些测试看起来好像一切都很好:

?> let lst = [Left 'c', Right 2, Left 'a', Right 3, Left 't']
?> let foo = SF $ map toUpper
?> let bar = SF $ map (+1)
?> runSF (left foo) lst
[Left 'C',Right 2,Left 'A',Right 3,Left 'T']
?> runSF (right bar) lst
[Left 'c',Right 3,Left 'a',Right 4,Left 't']

但使用它与mapA否则说:

?> let delay x = SF $ init . (x:)
?> runSF (mapA (delay 0)) [[1,2,3],[4,5,6],[7,8,9]]
[[0,0,0],[0,0,0],[0,0,0]]

正确答案应该是:

[[0,0,0],[1,2,3],[4,5,6]]

其中mapA定义为:

mapA :: ArrowChoice arr => arr a b -> arr [a] [b]
mapA f = arr listcase >>>
         (arr (const []) ||| (f *** mapA f >>> arr (uncurry (:))))

Answer 1

我不认为你的ArrowChoice实例是正确的.

注意,该delay函数接受一个流并替换第一个元素; 关键的是,它并没有完全相同地对待所有元素.现在,考虑一下你的定义Left:

left (SF f) = SF $ map (either (\x -> Left . head $ f [x]) Right)

观察这f是整个流函数的内核,因此可能根据流位置而表现不同.left然后,该函数创建一个新的流函数,该函数在其流上映射一个齐次函数,其中每个元素通过(用于Rights)或提升到运行输入流函数的单个列表.

而不是delay考虑以下功能:

skip = SF $ drop 1

这完全丢弃了流的第一个元素,并且由于left每次在单例列表上独立地运行其输入,这将Left完全过滤掉所有s!可能不是你想要的.

相反,您需要执行诸如将流分区为其组件Left和Right组件,将输入流函数应用于整个Left s 流,然后将lefts和权限以最初的相同顺序合并在一起.

我得到的印象是你正在做这种运动,所以我不会通过简单地完全解决问题来破坏乐趣.但我会说我的代码确实给出[[0,0,0],[1,2,3],[4,5,6]]了你的例子.

如果你想查看我的测试代码,请在下面.(嘘,它藏起来了)

 instance ArrowChoice SF where
     left (SF f) = SF $ \xs -> let (ls, rs) = partitionEithers xs 
                               in merge xs (f ls) rs
 
 merge (Left  _:xs) (l:ls) rs = Left l  : merge xs ls rs
 merge (Right _:xs) ls (r:rs) = Right r : merge xs ls rs
 merge _ _ _ = []