Co jest złego w tej implementacji quicksortu przy użyciu Arrows?

Question

Ok, więc pomyślałem o zabawie ze strzałami. Próbowałem bezpośrednio przetłumaczyć sexy quickscort Haskella do implementacji, która używa strzałek. Ale to nie działa poprawnie.

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 

Czy ktoś może zauważyć problem?

Answer 1

Problemem jest to, że tak naprawdę nie podzielić się z tail, dwa porównania nie są komplementarne. Staje się oczywiste, gdy piszemy pierwszy jako lambda, TOO:

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

po co chcesz to oczywiście

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

lub

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

BTW, wolałbym app ponad uncurry id.

Answer 2

Predykat pierwszego filtra jest nieprawidłowy.

(qs.) . filter . (<) 

powinny być

(qs.) . filter . (>)