问题使用Arrows实现快速排序有什么问题？

好的，所以我想到了带箭头的乐趣。我试图直接将性感的Haskell quicksort翻译成使用箭头的实现。但它无法正常工作。

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

有人能发现问题吗？

4654

2018-04-06 10:05

起源

答案:

问题是你没有真正分手了 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。

2018-04-06 10:56

大！知道这件事很好 app。谢谢：） - haskelline

答案:

问题是你没有真正分手了 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。

2018-04-06 10:56

大！知道这件事很好 app。谢谢：） - haskelline

第一个过滤器的谓词不正确。

(qs.) . filter . (<)

应该

(qs.) . filter . (>)

2018-04-06 10:55

问题 使用Arrows实现快速排序有什么问题？

答案:

答案:

热门问题

问题使用Arrows实现快速排序有什么问题？