Haskell - gregorymorrison/euler1 GitHub Wiki
Haskell, introduced in 1990, is the language that everyone says you should learn, because it will stretch your head. It's strictly functional, and everything is immutable. No, it's not named after Eddie Haskell, smartass - it's named after logician Haskell Curry (although when I invent my own language, I will be liberally sprinkling it with LeaveItToBeaverisms).
Rigid adherence to ideology is frustrating. In Java, having to construe everything as an object is a pain in the ass. If I just want to perform a simple function, I have to define and instantiate a functor class. Likewise, Haskell insists on side-effect-free code - all code must be deterministic. For a given input to a function, the function must always return the same output.
So, performing any operation in Haskell that has side effects, like IO, is a pain in the ass. Haskell makes you play a little semantics game. It uses monads, a complicated concept that can roughly be likened to encapsulation in OOP. All impure operations with side effects are isolated to these special constructs, which lets you assert the purity of the rest of your code. It's a concept that doesn't exist outside of Functional languages because other languages don't have the purity hangup. Haskell has built-in monads for common impure operations like IO; you can also write your own. Don't get too worked up about it, though - just note its existence for now. Here is a simple example of Euler1 using a list comprehension and a summation function:
-- Euler1 in Haskell
mySum [] = 0
mySum (x:xs) = x + mySum xs
euler1 (n) = mySum [x | x <- [0..n], x `mod` 3 == 0 || x `mod` 5 == 0]
main = do
let result = euler1 999
putStrLn $ "euler1 = " ++ show result
Note the (x:xs) syntax - this is borrowed from Lisp and Standard ML, and represents an array, where x represents the first element and xs represents the rest of the array.
Haskell does things that you've never seen in another language, like pattern matching. Mutiple methods with identical signatures, for example, are typically not allowed in other languages, but Haskell is quite happy with this. Haskell manages to resolve this discrepancy by defining a method with not just types, but actual values.
Here I've defined my own implementation of summation for illustration. The first two lines above define a function, mySum(), that takes one parameter, an array. When someone calls mySum with an array containing something, the runtime starts at the top of the program and works its way down, looking for a method instance that takes an array with something. It sees that the first line defines an instance of mySum that takes only an empty array and continues on. It then matches the method signature on the next line - the one with an array containing stuff. mySum matching a non-empty array will return the first element of the array plus mySum() called on the rest of the array. mySum matching an empty array returns 0.
Here's a different version using the IO.print monad. This one illustrates Haskell's optional strong typing. Haskell functions can return one value, so for a function signature with multiple values, all but the last are inputs. It uses the built-in right-fold function, and also generation of sequences from 0 to 999 counting by 3, 5, or 15. It subtracts the multiples of 15, since they're going the be the duplicate values found in the sequences of 3 and 5:
-- Euler1 in Haskell
mysum :: Integer -> Integer -> Integer
mysum mul lim = foldr (+) 0 [0, mul .. lim-1]
euler1 :: Integer -> Integer
euler1 (n) = mysum 3 n + mysum 5 n - mysum 15 n
main :: IO ()
main = do
let result = euler1 999
putStrLn $ "euler1 = " ++ show result
Here's a different version - I simply generate three arrays of ints up to 999, one step 3, one step 15 starting at 5, and one step 15 starting at 10. This covers all the ints divisible by 3 or 5 with no overlaps, and we simply sum them all up. Cool!
-- Euler1 in Haskell
euler1 :: Integer -> Integer
euler1 a = sum $ [3,6..a] ++ [5,20..a] ++ [10,25..a]
main :: IO ()
main = do
let result = euler1 999
putStrLn $ "euler1 = " ++ show result
Here's a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler() is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls. This version shows the use of guards - Haskell's version of a case statement for predicate values. Haskell actually does also have a case statement, though it is used for parameter-type pattern matching.
-- Euler1 in Haskell
euler :: Integer -> Integer -> Integer
euler n acc
| n == 0 = acc
| n `mod` 3 == 0 || n `mod` 5 == 0 = euler (n-1) (acc+n)
| otherwise = euler (n-1) (acc)
euler1 :: Integer -> Integer
euler1 n = euler n 0
main :: IO ()
main = do
let result = euler1 999
putStrLn $ "euler1 = " ++ show result
Here's another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler() returns euler() calculated on the half of the list before the pivot element, euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together:
-- Euler1 in Haskell
import Debug.Trace
debug = flip trace
slice :: [Int] -> Int -> Int -> [Int]
slice xs from to = do
let result = drop from $ take to xs `debug` ("slice: " ++ show xs ++ ", " ++ show from ++ ", " ++ show to)
result `debug` ("sliced: " ++ show result)
euler :: [Int] -> Int
euler xs =
if length xs == 0
then 0 `debug` ("returning 0")
else do
let pivot = (length xs) `div` 2
let pre = euler (slice xs 0 pivot)
let post = euler (slice xs (pivot+1) (length xs))
let pivotval = xs !! pivot
if pivotval `mod` 3 == 0 || pivotval `mod` 5 == 0
then pre + pivotval + post
else pre + post
euler1 :: Int -> Int
euler1 n = euler [1..n]
main :: IO ()
main = do
let result = euler1 999
putStrLn $ "euler1 = " ++ show result
Notice here that Haskell uses significant whitespace to define control flow. Haskell requires you to use indenting with spaces to define conditionals, loops, etc. This tripped me up quite a bit as my editor was set up to use tabs, and I kept getting mixed tabs and spaces. Make sure you fix your editor for spaces! Otherwise, Haskell will just spit out cryptic compiler messages like euler1_6.hs:11:25: error: parse error on input 'let', and cause you to pull out clumps of hair in frustration.
This version took me most of a day to write. I got tripped up with Haskell's array functions. Arrays are 0-based, and I had to write my own slice() function. Because of Haskell's insistence on no side effects, it doesn't play well with the standard printf-type debugging used in most languages. Still, it does need to provide some assistance, so I've left some debug output here as an example. Note, though, that Haskell will only print output once a function completes, so your print statements will probably be out of order. Also, print statements can't simply be dropped anywhere - they have to be related somehow to the return value. Note that my debug statements all either are at the return statement or where it is defined. WTF, Haskell? You really don't want to give anything away from your vaunted purity, I guess...
Haskell's implementation of Functional programming puts a big smile on my face. It's so straightforward and clean, it couldn't really be any simpler. First-class functions, lambdas, map, filter, reduce... everything in its right place:
-- Euler1 in Haskell
myMap :: Int -> Int
myMap x = x
myFilter :: Int -> Bool
myFilter x = x `mod` 3 == 0 || x `mod` 5 == 0
myFold :: Int -> Int -> Int
myFold x y = x + y
euler1 :: Int -> Int
euler1 size = foldr myFold 0 (filter myFilter (map myMap [1..size]))
main :: IO ()
main = do
let result = euler1 999
Let's rewrite the above using point-free notation. In point-free notation, function arguments are assumed so are not required. Note that euler() combines myMap(), myFilter(), and myFold() using function composition. And also note that myFilter() uses a lambda - an anonymous function. Fun fact: the use of the backslash before the x is supposed to represent the greek character lambda, λ.
-- Euler1 in Haskell
myMap :: [Int] -> [Int]
myMap = map (\x -> x)
myFilter :: [Int] -> [Int]
myFilter = filter (\x -> x `mod` 3 == 0 || x `mod` 5 == 0)
myFold :: [Int] -> Int
myFold = sum
euler :: [Int] -> Int
euler = myFold . myFilter . myMap
euler1 :: Int -> Int
euler1 size = euler [1..size]
main :: IO ()
main = do
let result = euler1 999
putStrLn $ "euler1 = " ++ show result
Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation:
-- Euler1 in Haskell
mysum :: Integer -> Integer -> Integer
mysum mul lim = ((lim `div` mul)^2 + (lim `div` mul)) * mul `div` 2
euler1 :: Integer -> Integer
euler1 n = mysum 3 n + mysum 5 n - mysum 15 n
main :: IO ()
main = do
let result = euler1 999
putStrLn $ "euler1 = " ++ show result
Despite the fact that I've read a lot about this language and thought that I would have no problem with it, I found that this exercise took me over a day to complete. The learning curve is steep, and the tools are not that forgiving. Still, this is undoubtedly a fun language. Give it a try. Plus, what's not to like about a language that's named after the coolest character in 'Leave It To Beaver'?
The instance of Haskell I'm using is the Glasgow Haskell Compiler - apt-get install ghc. Haskell seems to run amazingly fast. To run this code, you need to compile your code and then execute the resultant object file:
$ ghc -o euler1_hs euler1.hs
$ chmod +x euler1_hs
$ ./euler1_hs
233168