haskell - 这种使用箭头的快速排序实现有什么问题？

Question

好的，所以我想用箭头来找点乐子。我试图直接将性感的 Haskell 快速排序转换为使用箭头的实现。但它不能正常工作。

import Control.Arrow

qs :: Ord a => [a] -> [a]
qs = isEmpty >>> right (head &&& tail 
                        >>> first ((qs.) . filter . (<) 
                                   &&& (\x -> (x:) . qs . filter (>=x)))
                        >>> first (uncurry (&&&)) 
                        >>> uncurry id 
                        >>> uncurry (++)) 
             >>> extract
  where 
    isEmpty [] = Left []
    isEmpty x  = Right x
    extract (Left x)  = x
    extract (Right x) = x

有人能发现问题吗？

Answer 1

问题是您并没有真正拆分 tail ，这两个比较不是互补的。当我们将第一个也写成 lambda 时，这一点变得很明显:

first ( (\x -> qs. . filter (x<))
    &&& (\x -> (x:) . qs . filter (>=x)) )

当你想要的很明显

first ( (\x -> qs. . filter (<x))
    &&& (\x -> (x:) . qs . filter (>=x)) )

或者

first ( (qs.) . filter . (>)
    &&& (\x -> (x:) . qs . filter (x<=)) )

顺便说一句，我更喜欢 app超过 uncurry id .