Higher order functions

4th week of CIS 194 got into meat of functional programming: higher order functions. These are functions that either take other functions as parameters or return functions when called. While I was very familiar with them before, Haskell has neat trick in the sleeve for them. Topics covered included anonymous functions, function composition, partial application and folds (again).

Continue reading

Getting familiar with Prelude

Week 3 of CIS 194 was about how to abstract different kinds of recursion patterns with help of map, folds and filter. As a side note, polymorphism was touched upon to show how to define functions that work on several different kinds of data types. Prelude (one of the standard modules of Haskell) was mentioned and encouraged to be explored a bit. Finally total and partial functions were discussed and their differences outlined.

Continue reading

End of Vacation

The blog has been rather silent recently. Partly because I have been busy learning new things (Haskell mainly) and haven’t had anything to blog about, partly because of spending the vacation to go various places with my family. I haven’t worked on pyherc in a while, but I haven’t forgotten it. Next big thing it needs is a new partitioner that can split a level into different sized squares. After that I can reimplement the old and rather ugly looking catacombs level.

I started a side project, partly in order to learn Haskell and made a first release just recently. Space Privateers is now available in Hackage: https://hackage.haskell.org/package/SpacePrivateers. The game is sci-fi themed roguelike, set in distant future and it is built using the excellent LambdaHack engine. I learned some things about packaging and things like that from it, but actual Haskell coding I haven’t done much. I really would like to contribute to the engine, but first I really have to learn quite a bit more Haskell.

One thing I sort of miss is working with Hy. So I’m going to make more effort and catch up with the great community and see where the language is currently headed.

Validating credit card numbers with Haskell

No, I haven’t suddenly started running a web store. I wanted to have a break from Hy and miniKanren and decided to play around with the Haskell. After a bit of shopping around, I ended up reading notes of CIS 194: Introduction to Haskell. After the first set, I was supposed to write a function that can check credit card number for validity. Word of warning though, I have pretty much no clue what I’m doing here, so I probably get terminology horribly wrong.

The algorithm is simple:

Double the value of every second digit beginning from the right. That is, the last digit is unchanged; the second-to-last digit is doubled; the third-to-last digit is unchanged; and so on. For example, [1,3,8,6] becomes [2,3,16,6].

Add the digits of the doubled values and the undoubled digits from the original number. For example, [2,3,16,6] becomes 2+3+1+6+6 = 18.

Calculate the remainder when the sum is divided by 10. For the above example, the remainder would be 8.

If the result equals 0, then the number is valid.

So, first step is to take a number and turn it into an array of single digits. Following short code does that:

toDigits    :: Integer -> [Integer]
toDigitsRev :: Integer -> [Integer]

toDigitsRev n
  | n <= 0 = []
  | otherwise = n `mod` 10 : toDigitsRev (n `div` 10)

toDigits = reverse . toDigitsRev

Two first lines are used to define function types for toDigits and toDigitsRev. Both take a single parameter of type Integer and return a list of Integers. Strictly speaking they are not mandatory, but in case of errors, might help nailing down the exact location faster.

The next three lines are definition of toDigitsRev function. The single Integer type parameter (type isn’t repeated here though) is named n. Guard is the used to select how calculation is done (think of it as a type cond or switch-case). For values of n that are 0 or less, the result of toDigitsRev will be []. Otherwise a bit more involved calculation is used.

: is similar to cons in Lisp. It adds a new element at the start of a list. On the left side, we calculate modulo 10 of n (essentially a single digit from 0 to 9). On the right side, we call toDigitsRev again, this time using n divided by 10 as a parameter. Net effect is to pull the rightmost digit out, make a list that has that digit as a first element, and use rest of the number in a recursive call.

This worked just fine, except that the resulting list is of course reversed (hence the name toDigitsRev). Quick fix was to create another function that does the same thing and reverses the resulting list.

I could have written is as:

toDigits n = reverse(toDigitsRev n)

But instead of I chose to use following:

toDigits = reverse . toDigitsRev

Especially when function chains are very long, the latter might look much nicer to read.

Next step is to double every other digit:

doubleEveryOther :: [Integer] -> [Integer]

doubleEveryOther [] = []
doubleEveryOther (x:[]) = [x]
doubleEveryOther (x:y:zs) = x : (2 * y) : doubleEveryOther zs

So, a function that takes a list of Integers and produces a list of Integers. Here I chose to use pattern matching. There’s three different definitions of doubleEveryOther. Which of the will be used, depends on the given parameter.

In case of an empty list [], the function will return just an empty list [].

The second case matches when there’s a list, which last item is empty list (this is essentially a list with single item). In that case, the function returns what was given to it.

The third case is used when a list of three elements (last one can be empty, so [1, 2] will match) is used. It then builds a new list with first element left intact, second element being doubled and third element (can be empty) processed by doubleEveryOther.

But, we wanted to double every other digit, starting from right and the current solution starts from the left. Solution is simple, reverse the list before doubling the digits and reverse the resulting list (although, I wonder if there’s other way):

doubleEveryOtherRev = reverse . doubleEveryOther . reverse

Again I used function composition, instead of making a chain of function calls.

We’re pretty close to the solution, lets keep on building these functions and write one that can take a list of digits and sum them.

sumDigits :: [Integer] -> Integer

sumDigits [] = 0
sumDigits (x:xs)
  | x < 10    = x + sumDigits xs
  | otherwise = (x `mod` 10) + (x `div` 10) + sumDigits xs

This I’m not too happy with actually. SumDigits is a function that takes a list of Integers and returns an Integer. It recursively sums each and every item in the list. If entry is greater than 9, the function sums the digits instead of the number.

The last step is to tie all these functions together.

validate :: Integer -> Bool
validate n = (mod (sumDigits (doubleEveryOtherRev (toDigits n))) 10) == 0

This was pretty fun excercise. The resulting code looks pretty ok, but I bet there are lot of things that could be written more cleanly. Quite many of the functions are iterating through a list manually and there most likely is a better way of doing that.