Haskell: errors when trying to define a function with two arguments
I am trying to define a simple function that turns a list of single integers into one larger integer. For example, given the list [1,5,2,0], it will return 1520. For this, in base 10, I used:
calc_nr [] = 0
calc_nr (a:y) = a * 10^(length y) + (calc_nr y)
Now I wanted to expand this to different bases, which can be done by changing the base cardinality of 10 in the expression to the desired base. For this, I thought about accepting a different argument, b, and replacing the base power of 10 with the base power of b.
However, I am getting some errors when I try to do this. Record:
calc_nr b [] = 0
calc_nr b (a:y) = a * b^(length y) + (calc_nr y)
Gives me an error:
* Occurs check: cannot construct the infinite type: t ~ [t]
Expected type: [t] -> t
Actual type: t -> [t] -> t
* Relevant bindings include
calc_nr :: [t] -> t (bound at calc_nr.hs:39:1)
I'm new to Haskell, so it might be a pretty stupid mistake, but any help would be much appreciated!
source to share
First, some general guidelines:
-
Always write type signatures for top-level functions. This has many advantages (more on this later), but perhaps the most important is that someone reading your code will know what they are supposed to do. Your old fixed base-10 function would be
fromBase10rep :: [Int] -> Int
(You can also make it generic to work with other types of numbers besides
Int
, but I won't go into that to keep it simple.) -
Avoid unnecessary parentheses.
fromBase10Rep (a:y) = a * 10 ^ length y + calc_nr y
-
Also
length
, avoid indexing into lists. This is inefficient (the entire list needs to be iterated over every time you do this).
If you're just following the first point, you can probably answer the question yourself ...
fromBaseRep :: Int -> [Int] -> Int
fromBaseRep b [] = 0
fromBaseRep b (a:y) = a * b ^ length y + fromBaseRep y
because thanks to the type signature, the compiler can now give a much clearer error message:
/tmp/wtmpf-file21653.hs:3:42: error:
• Couldn't match expected type ‘Int’
with actual type ‘[Int] -> Int’
• Probable cause: ‘fromBaseRep’ is applied to too few arguments
In the second argument of ‘(+)’, namely ‘fromBaseRep y’
In the expression: a * b ^ length y + fromBaseRep y
In an equation for ‘fromBaseRep’:
fromBaseRep b (a : y) = a * b ^ length y + fromBaseRep y
|
3 | fromBaseRep b (a:y) = a * b ^ length y + fromBaseRep y
| ^^^^^^^^^^^^^
It basically tells you what the problem is: you've applied fromBaseRep
to too many arguments in a recursive call. He still needs to know which base should rearrange the rest of the room!
So just pass it b
over again and you should be fine.
fromBaseRep b (a:y) = a * b ^ length y + fromBaseRep b y
As I said, this is still ineffective due to the call length
. A good way to get around this is to multiply the left digits while they recursively go into the list:
fromBaseRep b = go 0
where go acc [] = acc
go acc (a:y) = go (b*acc + a) y
Note that delegating the recursion to the local "loop function" go
also allowed me to explicitly skip the pass b
- it was just reused from the binding fromBaseRep b = ...
.
This can also be written elegantly as a fold:
fromBaseRep b = foldl' ((+) . (b*)) 0
source to share