Что случилось с этой реализацией quicksort с помощью Arrows?

Хорошо, поэтому я подумал о том, чтобы повеселиться со стрелками. Я попытался напрямую перевести сексурированную операционную систему 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

Может ли кто-то выявить проблему?

Ответы

Ответ 1

Проблема в том, что вы действительно не разделяете tail, два сравнения не дополняют друг друга. Это становится очевидным, когда мы пишем первый как лямбда:

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.

Ответ 2

Предикат первого фильтра неверен.

(qs.) . filter . (<)

должен быть

(qs.) . filter . (>)