Dfyjkt

I'm trying to write Karatsuba Algorithm using the divide and conquer approach in Haskell. I did it with merge sort algorithm but can't figure it out here and it's a little bit embarrassing at this point.

My main function looks like this:

dz test end divide combine x = 
 if test x then end x
 else combine(map(dz test end divide combine) (divide x))

I test it for values 1234 and 5678: dz test end divide combine [1234, 5678,2].

So I have to write test, end, divide and combine functions.

lengthNumb x = length . show $ x
test (x:x1:xs) = (lengthNumb x) < 4 || (lengthNumb x1) < 4
end (x:y:z:xs) = [x * y, z]

This is pretty straightforward. I just check if both numbers that I want to multiply are at least 4 digits long. If not I just use simple multiplication and carry m value. I know that Karatsuba works better for bigger numbers but this is just for testing purposes.

divide = 
divide (x:x1:x2:xs) = 
 let y1 = x `div` 10^x2
 y2 = x `mod` 10^x2
 y3 = x2 `div` 2
 z1 = x1 `div` 10^x2
 z2 = x1 `mod` 10^x2
 in [[y1,y2,y3],[z1,z2,y3],[y1+y2, z1+z2, y3]]

combine [[x, x1],[y,y1],[z,z1]] = x * 10^(2*x1) + y + (z - x - y) * 10^x1

I was told that combine function should only do the final multiplication. So I guess it should get three numbers as an input (each with their m value) and then also do the necessary subtraction ( z-x-y ) because I couldn't do it in divide.

But this is wrong. I get an error:

Occurs check: cannot construct the infinite type: a ~ [a]
 Expected type: [[a]] -> [a]

 Actual type: [[[a]]] -> [a]

I think it is a problem with the parameters of combine function but I don't know how to fix it. I also think that there could be a problem with how combine and divide work together because in one of the previous iterations the final result of multiplication was wrong.