Skip to content

Instantly share code, notes, and snippets.

@deque-blog

deque-blog/merge_monoid_with_fold2.hs

Created December 22, 2016 19:50
Show Gist options
  • Save deque-blog/de3f6ddd630a118912d6b4e4b2875b9e to your computer and use it in GitHub Desktop.
Save deque-blog/de3f6ddd630a118912d6b4e4b2875b9e to your computer and use it in GitHub Desktop.
Download ZIP
Raw
merge_monoid_with_fold2.hs
newtype SortedList a = SortedList { unSortedList :: [a] }
instance (Ord a) => Monoid (SortedList a) where
mempty = SortedList []
mappend (SortedList a) (SortedList b) = SortedList $ merge a b
foldMergeSort :: (Ord a) => [a] -> [a]
foldMergeSort = unSortedList . foldMonoidTree . map (\x -> SortedList [x])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment