Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Haskell mergesort

Name: Anonymous 2012-04-24 5:29

Haskell newbie here, how is my mergesort?


merge :: (Ord a) => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if (x < y) then x:(merge xs (y:ys)) else y:(merge (x:xs) ys)

mergeSort :: (Ord a) => [a] -> [a]
mergeSort []  = []
mergeSort [x] = [x]
mergeSort xs  = let mid   = (length xs) `div` 2
                    parts = (splitAt mid xs)
                    left  = mergeSort (fst parts)
                    right = mergeSort (snd parts)
                in merge left right

Name: Anonymous 2012-04-24 5:33

test

Name: Anonymous 2012-04-24 6:03

What a great mergesort!!

Name: Anonymous 2012-04-24 6:26

>>3
And how!

Name: Anonymous 2012-04-24 6:51

mergeSort' :: (Ord a) => [a] -> [a]
mergeSort' [] = []
mergeSort' (x:[]) = [x]
mergeSort' xs = merge left right
    where mid = length xs `quot` 2
          left = mergeSort' $ take mid xs
          right = mergeSort' $ drop mid xs
          merge [] ys = ys
          merge xs [] = xs
          merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys)
                              | otherwise = y : merge (x:xs) ys

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-04-24 11:19

Taking the length of a list is an Java/C/C++ thing. In haskell, you can avoid the inefficient traversal by taking the tuple of a list.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-04-24 11:21

>>6
Look ma, I know more than Java!

Name: Anonymous 2012-04-24 12:10

>>6
go scrub another haskell faggot you mental goy

Name: Anonymous 2012-04-24 12:12

>>8
You're just mad because I saw something in the original code that you didn't.

Name: Anonymous 2012-04-24 12:57

>>9
I didn't even read the original code.  Your move, faggot.

Name: Anonymous 2012-04-24 13:33

>>10
Let me guess, you don't have the IQ to undersand a real language like Haskell.

Name: Anonymous 2012-04-24 13:36

>>11
It's shit, son.

Name: Anonymous 2012-04-24 14:26

>>12
How would you know? Have you ever even tried to write anything in Haskell? I would venture to say no because you didn't see the misuse of 'length' in the original code.

Name: Anonymous 2012-04-24 15:05

>>13
The fact that using 'length' on lists doesn't get properly optimized in a purely functional programming language really just means it's pure shit, and that you are a humongous faggot.

Name: Anonymous 2012-04-24 15:16

>>14
Go away. You are both dumb and boring.

Name: Anonymous 2012-04-24 15:51

>>11
>IQ to undersand a real language like Haskell
­>230 ?

Name: Anonymous 2012-04-24 15:57

sort = sortBy compare
sortBy cmp = mergeAll . sequences
  where
    sequences (a:b:xs)
      | a `cmp` b == GT = descending b [a]  xs
      | otherwise       = ascending  b (a:) xs
    sequences xs = [xs]

    descending a as (b:bs)
      | a `cmp` b == GT = descending b (a:as) bs
    descending a as bs  = (a:as): sequences bs

    ascending a as (b:bs)
      | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
    ascending a as bs   = as [a]: sequences bs

    mergeAll [x] = x
    mergeAll xs  = mergeAll (mergePairs xs)

    mergePairs (a:b:xs) = merge a b: mergePairs xs
    mergePairs xs       = xs

    merge as@(a:as') bs@(b:bs')
      | a `cmp` b == GT = b:merge as  bs'
      | otherwise       = a:merge as' bs
    merge [] bs         = bs
    merge as []         = as

Name: Anonymous 2012-04-24 18:06

>>15
No, you go away you piece of shit.

Name: Anonymous 2012-04-24 18:25

>>18
The only thing that you've contributed to this thread are insults. This is because Haskell is too much programming language for you.

Name: Anonymous 2012-04-24 19:11

>>19
Haskell is shit and you are a fucking fag.

Name: Anonymous 2012-04-24 20:10

>>20
This is coming from a no talent nigger who hasn't never written a single line of Haskell code.

Name: Anonymous 2012-04-24 20:38

hasn't never

Name: Anonymous 2012-04-24 21:47

>>22
nice dubz

Name: Anonymous 2012-04-24 21:54

sight*, if you are _that_ concerned about the length, it's only
expensive the first time you call it, after that is only as
expensive as in any other language. you could pass the result
the first time, but that's an extra optimization (but it just a closure away)

OP: is ok as a mergersort. nothing to add.

also don't be afraid to use length in a sorting function, information theory tells us that every element of the data-structure must be compared against every other one, so it obvious that you data-structure needs to be finite, (try sort on [1..])

Name: Anonymous 2012-04-24 21:59

>>24

GHCi, version 7.4.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :set +s
Prelude> let a = [1..500000]
(0.01 secs, 5983280 bytes)
Prelude> length a
500000
(0.10 secs, 43996048 bytes)
Prelude> length a
500000
(0.01 secs, 587544 bytes)

Name: Anonymous 2012-04-24 22:50

>>24 if the comparison function is cheap, merge sort with an O(n) length function being called in each recursive branch will be noticably slower than a merge sort that either uses a O(1) length function, or doesn't use the top down divide and conquer method. It is easiest to do bottom up merging, like in >>17. But the merge sort will still run in O(nlog(n)), even with the length calculation. You can afford for the merge operation to take linear time, and the length call doesn't do worse than that.

Name: Anonymous 2012-04-24 23:24

>>24
if you are _that_ concerned about the length
measure it everyday, it makes /prog/ less SEPPLES.

Name: bampu pantsu 2012-05-29 4:36

bampu pantsu
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -