CODEWITHSUNDEEP
haskellarrow-abstraction
haskelline
haskelline

Reputation: 1136

What's wrong with this implementation of quicksort using Arrows?

Ok, so I thought of having some fun with arrows. I tried to directly translate the sexy Haskell quicksort to an implementation that uses arrows instead. But it does not work correctly.

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

Can someone spot the problem?

Upvotes: 11

Views: 430

Answers (2)

leftaroundabout
leftaroundabout

Reputation: 120711

The problem is that you don't really split up the tail, the two comparisons aren't complemental. It becomes obvious when we write the first one as a lambda, too:

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

when what you want is obviously

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

or

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

BTW, I'd prefer app over uncurry id.

Upvotes: 6

snak
snak

Reputation: 6703

The predicate of the first filter is incorrect.

(qs.) . filter . (<)

should be

(qs.) . filter . (>)

Upvotes: 6

Related Questions