Sortable

From Listable to Sortable

Once there is a notion of Listable with its methods acting on its instances like lists,
the notion of Sortable is a natural extension. Here I extend Listables to have behaviors such as sort and shuffle. The sort is a quicksort and the shuffle is a key shuffle.

import System.Random
:l Listable

System.Random is imported here as a method for producing a stream of random numbers is required for a key shuffle.

The next few lines gives a function which produces such a stream. Notice, I am not yet concerned about a random seed.

randos :: [Integer]
randos = randomRs (0, 10^6) $ mkStdGen 32

take 10 randos
[279768,3864,196758,671882,495589,457372,652070,194519,28935,96049]

Next, I introduce the class Sortable. Notice that most ‘special’ methods are supplied by Listable. The Sortable methods are gotten ‘for free’. Lastly, instances of Sortable [a] and Integers are given. The one caveat being that Ord a => [a].

class (Ord s, Listable s) => Sortable s where
  sort, shuffle :: s -> s

  sort ns | ns == unit = unit
          | otherwise = branch smaller ns +++ headL ns +++ branch larger ns
    where
      branch f xs = sort.f (headL xs) $ tailL xs
      smaller n = filterL (<= n)
      larger  n = filterL (>  n)

  shuffle = eval . map snd . sort . zipS randos
    where
      eval = foldr cons unit
      zipS [] s = []
      zipS (x:xs) s | s == unit = []
                    | otherwise = (x, headL s) : zipS xs (tailL s)
                    
instance Sortable Integer where
instance Ord a => Sortable [a] where
sort 23478662345
shuffle 23423423
shuffle [1..10]
sort.shuffle $ [1..10]
22334456678
33243422
[2,9,8,3,1,6,5,7,4,10]
[1,2,3,4,5,6,7,8,9,10]

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s