Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An attempt at an bottom-up functional representation of mergesort
import Control.Arrow
import Data.List
import Data.Function
main = interact (show.(mergeSort (<=)).head.lines)
merge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
merge _ xs [] = xs
merge _ [] ys = ys
merge p (x:xs) (y:ys) =
if x `p` y then x: merge p xs (y:ys) else y: merge p (x:xs) ys
longer :: [a] -> [a] -> Bool
longer [] _ = False
longer (_:_) [] = True
longer (_:xs) (_:ys) = xs `longer` ys
merge' :: (a -> a -> Bool) -> [[a]] -> [a] -> [[a]]
merge' _ [] ys = [ys]
merge' p (xs:xss) ys =
if xs `longer` ys then ys:xs:xss else merge' p xss $ merge p xs ys
mergeSort :: (a -> a -> Bool) -> [a] -> [a]
mergeSort p xs = foldl (merge p) [] $ foldl (merge' p) [] $ map (:[]) xs
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.