Cosa c'è di sbagliato in questa implementazione di quicksort usando le frecce?

Question

Ok, quindi ho pensato di divertirmi con le frecce. Ho provato a tradurre direttamente il quicksort sexy Haskell in un'implementazione che utilizza invece le frecce. Ma non funziona correttamente.

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 

Qualcuno può individuare il problema?

Answer 1

Il problema è che non si ha realmente dividere la tail, i due confronti non sono complementare. Diventa evidente quando scriviamo il primo come un lambda, troppo:

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

quando ciò che si vuole è ovviamente

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

o

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

BTW, io preferirei app oltre uncurry id.

Answer 2

Il predicato del primo filtro non è corretto.

(qs.) . filter . (<) 

dovrebbe essere

(qs.) . filter . (>)