4 replies to this topic

[Defenestrayte]

Right, so I wrote a function for a merge sort using haskell,
and i found that the _mergeSort function was simply refusing
to compile... interpret... whatever...

It was complaining about the first line of code after the rev function
It wouldn't work unless one more parameter was added to
the _mergeSort function... one which _mergeSort doesnt ask for

sorry for the possibly terrible style issues.
I'm a java student at base and I'm just meddling trying to get things to work,
Now they work I'm screaming trying to figure out why.
cause they shouldnt work.

please do note, this code does work :P

**edit, simplified the split by adding _split

mergeSort [] = []

mergeSort [x] = [x]




mergeSort x = _mergeSort (split x) []  --  <-problem is this empty array here

--- I CANNOT figure out why the last empty string has decided to need to be here.

--- my function doesnt ask for it....(see next line)... but it complains when ever it's 

---taken away  


_mergeSort (x, y) = merge (mergeSort x, mergeSort y) [] 



--- merges two arrays together, putting the higher of the two head values in the results first


merge (x:xs, y:ys) ls

  |x<=y 	    = merge (x:xs, ys) (y:ls)

  |otherwise 	    = merge (xs, y:ys) (x:ls)


merge ([], y:ys) ls = merge ([], ys) (y:ls)

merge (x:xs, []) ls = merge (xs, []) (x:ls)

merge ([], []) ls = (rev' ls)  ---  <- noticed here I was using rev' rather than rev. changed it, 

---now everything is sorting in the opposite direction (as i expected originally) 

--- and it now only compiles if the mystery empty bracket(my original problem) is removed...





---reverses values in an list

rev l = rev' l []

rev' [] r = r

rev' (x:xs) r = rev' xs (x:r)



---splits the array in two and returns them as a dual-array tuple

split (x:y:ls) = split (x:y:ls) [] []

_split (x:y:ls) [] [] = split ls [x] [y]

_split (x:y:ls) a b = split ls (x:a) (y:b)

_split [x] a b = ((x:a), b)

_split [] a b = (a, b)

**edit2** Umm ok, problem solved, but no less confused... I changed one of my functions and now everything is happy and cheerful, except the function has nothing to do with the original problem area..

should I dismiss as ghosts in the code?

Edited by Defenestrayte, 16 March 2011 - 11:11 PM.

[Defenestrayte]

Double posting yes, but thought I should refine what different ways I fixed this,
I'm assuming that I've fallen through a crack in the interpreter into unknown realms with this problem,

Fixes:
1) replace rev' with-> rev --line 123
and remove the mystery array
2) replace rev' ls with-> rev' ls [] --line123
and remove the mystery array
3) leave as is and ignore the fact that it is oh so wrong...

if you come up with a explanation/hypothesis/wild-goose-chase please post ^_^
-for science, you monster-

[ZekeDragon]

Okay, I WILL now explain what happened to you, because yes, the way you wrote it was mergeSort DID have another argument, because you used rev' instead of rev.

Remember that in Haskell it is perfectly legitimate to return a function as a return type, including a curried function. Your _mergeSort algorithm ultimately just calls merge with different arguments, and every branch of merge's pattern match will call itself recursively except the last one, which returns rev' lst, a curried function. When you only apply one argument to rev', it's still expecting it's other argument, but that's okay as it will get this argument down the line. This is known as function currying, it's very useful. Consider this in the standard library:

foldl f v (x:xs) = f (f v x) xs

foldl _ v []     = v


sum = foldl (+) 0

If you look above, you'll notice foldl requires 3 arguments, but sum only provided it two. This is because sum awaits as it own, undeclared, argument as required by foldl. Make sense?

Haskell's type inference sometimes makes this difficult to see, try explicitly declaring your type signatures for some functions when you have this happen, then you'll have a better idea of where the REAL problem is:

[b]mergeSort :: (Ord a) => [a] -> [a][/b]

mergeSort [] = []

mergeSort [x] = [x]

mergeSort x = _mergeSort (split x)


[b]_mergeSort :: (Ord a) => ([a], [a]) -> [a][/b]

_mergeSort (x, y) = merge (mergeSort x, mergeSort y) [] 



--- merges two arrays together, putting the higher of the two head values in the results first

[b]merge :: (Ord a) => ([a], [a]) -> [a] -> [a][/b]

merge (x:xs, y:ys) ls

  |x<=y 	    = merge (x:xs, ys) (y:ls)

  |otherwise 	    = merge (xs, y:ys) (x:ls)


merge ([], y:ys) ls = merge ([], ys) (y:ls)

merge (x:xs, []) ls = merge (xs, []) (x:ls)

merge ([], []) ls = (rev' ls)  ---  <- noticed here I was using rev' rather than rev. changed it, 

---now everything is sorting in the opposite direction (as i expected originally) 

--- and it now only compiles if the mystery empty bracket(my original problem) is removed...





[b]rev :: [a] -> [a][/b]

---reverses values in an list

rev l = rev' l []


[b]rev' :: [a] -> [a] -> [a][/b]

rev' [] r = r

rev' (x:xs) r = rev' xs (x:r)

[Defenestrayte]

So what I think im getting(there was one sentance i didnt quite get, I think i got the rest...ish) is that because I didnt give rev' another parameter it just allowed it as long as somewhere up the line(at the top of the call stack where it is used?) one of the calling methods provided that extra parameter?

could you repeat this example? I didnt quite understand the last sentance of the explanation and .. this sounds interesting :)

Quote

foldl f v (x:xs) = f (f v x) xs

foldl _ v []     = v


sum = foldl (+) 0

If you look above, you'll notice foldl requires 3 arguments, but sum only provided it two. This is because sum awaits as it own, undeclared, argument as required by foldl. Make sense?

Cheers by the way, good to know I'm not just breaking all the things ^_^

[ZekeDragon]

Okay, to understand this I think the easiest way is to understand (what I call) the Replacement Principle, which essentially means anywhere you use a named function, you could have also used an unnamed equivalent of the same function. Consider if we had a function called "addFiveTo", that added 5 to any passed value:

addFiveTo x = x + 5

Now you can use this normally anywhere in your program.

main = getLine >>=

       putStrLn . show . addFiveTo . read

If you were to replace addFiveTo with an anonymous, unnamed function, it would be equivalent.

main = getLine >>=

       putStrLn . show . (\x -> x + 5) . read

You can of course shorten this code if you remember working with operators. An Operator can be put in between parenthesis to make it act like a normal function (IE turn it to prefix notation instead of infix). You can also give it either argument when you do so.

main = getLine >>

       putStrLn . show . (+5) . read

Now you've got something really easy... but wait, the Replacement Principle says it's possible to do this with addFiveTo as well.

addFiveTo = (+5)

And there was no need to explicitly name any arguments! Functions are perfectly legitimate to return from another function, so if you check addFiveTo's type, it'll be as follows:

addFiveTo :: (Num a) => a -> a

Or, if you compiled it or ran it in ghci, more likely this:

addFiveTo :: Integer -> Integer

Simply put, addFiveTo returns, as a value, the function (+5). This is then applied to the subsequent arguments that follow the call to addFiveTo.

Edited by ZekeDragon, 18 March 2011 - 08:39 PM.