This one doesn't warrant much discussion:

Problem 16:
What is the sum of the digits of the number 2^1000?

problem15 = sum . digits (2^1000) where
    digits n = map (\x -> read [x] :: Int) $ show n

Now for a much more interesting problem (deja vu?):

Problem 18:
Find the route from top to bottom with the largest sum in the triangle below:
   75
95 64
...

The triangle has 15 rows, so it's not unreasonable to simply brute force it. We could go about this by recursively asking a node in the triangle for the greater of its two child routes, e.g. a function like this:

maxRoute node
    | noChildren node = node
    | otherwise       = node + max (maxRoute leftChild) (maxRoute rightChild)

Unfortunately, we can't just pass a simple number to maxRoute, because there would be no way of determining what leftChild and rightChild are. I'm sure we could accomplish it using some sort of custom-defined type, but I haven't read up on defining custom types in Haskell. Instead, we'll just pass a pair of coordinates, which we can use to lookup the value in our triangle data structure (which will be a simple two-dimensional list):

maxRoute row col
    | row == 14 = tri !! row !! col
    | otherwise = tri !! row !! col + max left right where
        left  = maxRoute (row + 1) col
        right = maxRoute (row + 1) (col + 1)
    tri = [[75],
           [95,64],
           [17,47,82],
           ...

Then a simple problem18 = maxRoute 0 0 will compute the answer.

A more sophisticated approach would be to go "bottom up" instead of "top down," as in the brute force strategy. Starting at the bottom of the triangle, we reduce each parent-left-right set with parent = parent + max left right. Then we can simply fold this operation upwards until we reach the top of the triangle, at which point we'll have our answer.
This algorithm winds up looking a bit more complex, mainly because now we're processing two whole rows at a time instead of just three nodes. That means we'll be using zipWith3, which works as you might expect. The function we'll be zipping with is exactly what we described above, and the list arguments will be the parent row, the child row, and the child row with an offset of 1 (via tail).

problem18 = head $ foldr1 maxRow tri where
    maxRow pRow cRow = zipWith3 reduce pRow cRow (tail cRow)
    reduce parent left right = parent + max left right
    tri = [[75],
           [95,64],
           [17,47,82],
           ...

Note that we have to use foldr instead of the usual foldl since we're starting at the bottom.

Let's finish off this post with another easy one:

Problem 20:
Find the sum of the digits in the number 100!

This is as easy as:

problem20 = sum . digits $ factorial 100

...except that we haven't defined a factorial function yet. In an earlier post, we covered a few methods of implementing a factorial function in Perl. As it turns out, it's even more fun in Haskell (in fact, there's an entire web page devoted to it). Let's cover just a few:

fac 0 = 1
fac n = n * fac (n - 1)

fac n = product [1..n] -- essentially syntactic sugar for:
fac n = foldl1 (*) [1..n]

facs = scanl (*) 1 [1..]
fac n = facs !! n

Efficiency-wise, it doesn't make much difference which implementation you choose, but if you're going to computing lots of values, the memoized version (that last one) is probably your best bet. Memoization means that before carrying out the factorial computation, we first check to see if we already know the answer. Then we can just use that instead of recalculating it from scratch. In most languages, a memoized implementation of factorial will be quite a bit more verbose, but it comes almost for free in Haskell because of the lazy nature of infinite lists. fac is just looking up a value in facs, and when we ask facs for an entry it hasn't calculated yet, it carries out the necessary computation. So asking for fac 10000 might take a bit, but after that you'll be able to look up any factorial under 10000 almost instantly. Pretty cool!

First post in months! Now that school is done with I should be able to bang out some more of these. Let's get right down to it then, shall we?

Problem 13:
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers:
37107287533902102798797998220837590246510135740250, 46376937677490009712648124896970078050417018260538, 74324986199524741059474233309513058123726617309629 ...

Straightforward enough. Summing lists of numbers is nothing new to us, and it turns out that we only need the first 11 digits or so to get the accuracy we need:

problem13 = take 10 . show . sum $ numbers where
    numbers = [37107287533, 46376937677, 74324986199, ... ]

Now for a much more interesting problem:

Problem 14:
A Collatz chain is an iterative sequence that obeys the following rules:
  -  n → n/2 (if n is even)
  -  n → 3n + 1 (if n is odd)
  -  The sequence ends when n = 1
Which starting number, under one million, produces the longest Collatz chain?

What is the best way to approach this problem? One method would be to write a function that produces the next value in the Collatz chain. We could then use iterate to generate the full sequence:

nextCollatz n
    | even n = n `div` 2
    | odd n  = 3*n + 1

collatzChain n = takeWhile (/= 1) $ iterate nextCollatz n

and use a list comprehension to obtain the longest chain:

problem14 = maximum [ (length (collatzChain x), x) | x <- [1..1000000] ]

Alternatively, we could rewrite our nextCollatz function to do the list-generating itself. Then we wouldn't need a separate chaining function to string the values together:

collatzChain 1 = [1]
collatzChain n
    | even n = n : collatzChain (n `div` 2)
    | odd n  = n : collatzChain (3*n + 1)

However, it turns out that the former version runs just a hair faster.
Next problem:

Problem 15:
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?

Oh boy. This is an interesting one. If you're a functional programmer, your first instinct should be to model this as a recursive problem. At each intersection, the number of paths to the bottom right corner is just the sum of the value below and the value to the right, so we can work backwards to find the total sum at the top left corner. On the other hand, the more mathematically inclined may notice that the value at each intersection can be computed without the need for recursion, using the formula factorial n `div` (factorial n/2)^2.
If you are a true Haskell wizard, though, there is another solution:

problem15 = (iterate (scanl1 (+)) (repeat 1)) !! 20 !! 20

It should blow your mind that we can compress this problem down to essentially just a scanl and an iterate. Note the array indices: we are actually constructing an infinite grid of route numbers and then extracting the value for a 20x20 grid. We can shed some light on how it works by examining just the subset of the infinite grid that we're interested in:

take 20 $ iterate (scanl1 (+)) $ take 20 (repeat 1)
[1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
[1, 2, 3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91,105,120,136,153,171,190,210]
...

The iterate and scanl1 combine to implement the "sum" that we discussed earlier. In a way, you can think of scanl1 as adding the left value, and iterate as adding the above value. Super cool!

Let's do two easy problems and then a harder one.

Problem 9:
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which a^2 + b^2 = c^2. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

We can accomplish this by using a simple list comprehension to enumerate all the Pythagorean triplets that fit these constraints:

[ [a,b,c] | a <- [1..999], b <- [1..a], let c = 1000 - a - b, a^2 + b^2 == c^2]

Since we know that a + b + c = 1000, we can define c in terms of a and b. We can also avoid doing excessive computation by taking b from the range [1..a] instead of [1..999]. Once we have our set of three numbers, it's a simple matter of multiplying them together to get the final answer:

problem9 = product $ head [ [a,b,c] | a <- [1..999], b <- [1..a], let c = 1000 - a - b, a^2 + b^2 == c^2]

The next one is even easier:

Problem 10:
Find the sum of all the primes below two million.

We already covered a method for generating primes, so our solution is just:

problem10 = sum $ takeWhile (<2000000) primes

And now for a slightly trickier problem:

Problem 12:
What is the value of the first triangle number to have over five hundred divisors?

(Yes, I skipped over problem 11. I haven't found a good way of doing it yet.)
The triangular numbers can be easily generated using scanl1. To find the number of factors of a number, we use the following trick: find the prime factorization of the number, add 1 to each exponent in the factorization, then multiply the exponents together. This makes sense because any factor must be a combination of prime factors. So really you're evaluating all the possible combinations of exponents in the prime factorization, with each term pⁿ having n+1 possible exponent states (since n = 0 is also a valid state).

The only real challenge here is to find a way get the exponents of each prime factor. Recall that our primeFactors function returns a unique list of prime numbers that multiply together to form the original number. So one way we can get the exponent of each number is to simply count the number of times a number appears in the list. To accomplish this, we will use a new function called span, which takes a list and a comparison as arguments and returns a tuple.

Have we covered tuples yet? A tuple is just a pair of two values. The reason they're useful is that the values can have different types, which isn't true of a list. In this case, span looks for the first element in the list that does not satisfy the comparison function, and splits the list in two at that element. The first part goes in the first value of the tuple, and the latter part goes to the second value.

Normally we could not use span to count the number of occurrences of an element in a list, but this is a special case. Since the way we defined primeFactors means that its output is in ascending order, the repeated prime factors will already be grouped together. So all we have to do is get the length of the first part, then call our function on the latter part to get the next value. Here's the implementation:

getExp [] = []
getExp xs = length (fst spanTuple) : getExp (snd spanTuple) where
    spanTuple = span (== (head xs)) xs

As you might have guessed, fst and snd are simply functions that let us access the first and second values in a tuple. Also note that we must define the base case getExp []; otherwise our function would never terminate.

Now that we have our list of exponents, it is a simple matter to add 1 to them and take the product. Then we simply run this calculation on each triangular number and perform a list comprehension:

problem12 = head [x | x <- triangles, numFactors x > 500] where
    triangles = scanl1 (+) [1..]
    numFactors = product . getExp . primeFactors
    getExp [] = []
    getExp xs = length (fst spanTuple) : getExp (snd spanTuple) where
        spanTuple = span (== (head xs)) xs

Note that we have defined numFactors in pointfree style here.

Originally I used group to count the number of occurrences, but it seemed unnecessarily verbose. Fortunately, Haskell makes it easy to define custom-tailored functions like getExp inline, right where you need them.

For this problem we're going to string together the longest chain of functions we've seen yet. Don't be intimidated though, it's pretty straightforward.

Problem 8:
Find the greatest product of five consecutive digits in the 1000-digit number: 73167176531330624919225119674426574742355349194934...

Our strategy is this: make a list that contains the digits of this number. Then make four more copies of this list, each missing the head of the previous list. Then multiply all the lists together and take the maximum result as our answer.
If that's a bit confusing, no worries. It will make more sense when we go through an example.
First though, we need a way of creating a list of digits out of one big number. To do this, we first convert the number to a string using show. Since a string is just a list of chars, we can then map read onto each value to change it back to an int.

digits n = map convertToInt $ show n where
    convertToInt x = read [x] :: Int

That new syntax after read just signifies that we are casting the char to an int, and not something else.
There is a better way to write this function, however. Instead of making a separate convertToInt function, we can use a lambda instead. A lambda is an unnamed (anonymous) function that we can use once and then forget about. To declare a lambda we use \, since it kinda looks like a lambda (some Haskell IDEs actually replace the \ with a λ).

digits n = map (\x -> read [x] :: Int) $ show n

As you can see, it's almost identical to the function definition before, except that we replaced the = with ->.
Lambdas are so cool that there's actually an entire domain of mathematics called Lambda Calculus that deals with them. If that sort of thing interests you, there's a good primer here.
Anyway, now we can actually implement our algorithm. We'll start by introducing a new function, iterate, that creates an infinite list by repeatedly applying a function to its argument. For example, if your function was (+2) and your argument was 1, iterate would generate the infinite list [1,3..]. Here, our function of choice is tail. Thus, if our number was 123456789, our new list would be:

[123456789,
  23456789,
   3456789,
    456789,
       ...]

(Okay, technically the result is a list of lists, with each list containing one digit per element, but you get the idea). Of course, in this case the list is not infinite, since eventually the list will be empty; asking for any subsequent values will cause an error, since the tail of an empty list is undefined. Fortunately, we only need the first five results, and Haskell's lazy nature allows us to avoid the error:

take 5 . iterate tail . digits number

Now, we just need to multiply the resulting lists together. This can be accomplished using a fold and zipWith. zipWith lets us multiply together the corresponding indices of two lists, and foldr1 (or foldl1) lets us apply this to operation to all five lists. Here's a nice visualization:

  1,2,3,4,5,6,7,8,9 -> 2,6,12,20,30,42,56,72 -> 6,24,60,120,210,336,504 ...
* 2,3,4,5,6,7,8,9    * 3,4, 5, 6, 7, 8, 9     * 4, 5, 6,  7,  8,  9
  3,4,5,6,7,8,9        4,5, 6, 7, 8, 9          5, 6, 7,  8,  9
  4,5,6,7,8,9          5,6, 7, 8, 9
  5,6,7,8,9

Highlighted in yellow are all the possible sequences that we could multiply together (you should read it vertically, although it also works horizontally in this case). The other numbers are dropped because zipWith truncates the result to match the shorter list.
We can then simply apply maximum to obtain our final result:

problem8 = maximum . foldr1 (zipWith (*)) $ take 5 . iterate tail . digits $ number where
    number = 73167176531330624919225119674426...

That's a lot of composition! The trick is to just read it right to left and think about what the intermediate results will look like.

The next few problems are pretty easy, so I think we can knock out four (!!!) in one post.

Problem 4:
A palindromic number reads the same both ways. Find the largest palindrome made from the product of two 3-digit numbers.

A simple list comprehension accomplishes this. We can test for symmetry by using show, which converts a value to a string, and reverse.

[x | y <- [100..999], z <- [y..999], let x = y * z, show x == reverse (show x)]

let allows us to define local variables, similar to where.
We can improve the efficiency of this code by an order of magnitude by observing that any six-digit palindrome will be a multiple of 11, since it will be of the form 100001a + 1001b + 11c = 11*(9091a + 91b + c). Then we simply add a maximum and we're done:

problem4 = maxmimum [x | y <- [110,121..999], z <- [y..999], let x = y * z, show x == reverse (show x)]

Problem 5:
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

This one is laughably trivial in Haskell, thanks to the built in lcm function:

problem5 = foldl1 lcm [1..20]

Folding a list is a common operation in functional languages. First, lcm is applied to 1 and 2, whose least common multiple is 2. Then lcm is applied to 2 and 6, yielding 6, and so on. It's almost identical to scanl1, except that it just returns the final result instead of a list of intermediate values (in other words, foldl1 = last . scanl1).

Problem 6:
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

No explanation needed:

problem6 = (sum [1..100])^2 - (sum $ map (^2) [1..100])

And finally, the most trivial of them all (since we already wrote a prime generating function last time):

Problem 7:
What is the 10,001st prime number?

problem7 = primes!!10000 where
    primes = sieve [2..] where
        sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

Of course, this may take a while to execute, since we are using a rather simplistic algorithm. It's certainly faster than our Perl approach, though!

Same problem set, different day.

Problem 3:
What is the largest prime factor of the number 600851475143?

Like those before it, this problem can easily be solved with a list comprehension (though in this case we need a way of generating prime numbers). Just examine all the prime divisors less than the square root of 600851475143, and pick out the largest one:

problem3 = last [ x | x <- takeWhile (<= (floor $ sqrt 600851475143)) primes, 600851475143 `mod` x == 0]

We have to use floor here because sqrt doesn't return an integer. Note the $ syntax we use for applying a function to the output of another function. There is also ., which composes two functions. The distinction between them is a fine one, but it's important. Essentially, $ is just "syntactic sugar" that replaces a pair of parentheses, so floor $ sqrt x is equivalent to floor (sqrt x). Function composition is another matter: the output of one function is passed directly to the input of another. This means that their data types must match. And the . operator is not merely syntactic sugar, it is a real function that returns a new function.
At any rate, this solution works, but it is lacking. First of all, we didn't discuss a method of generating primes. But more importantly, it's just too slow. The square root is 100 times larger than the largest prime divisor, so we are wasting a lot of effort.
There is a faster approach, but it's a bit more complicated. The concept is that we can save a lot of time by stopping once our list of divisors multiplies up to the original number. We'll reuse the same list comprehension from before, and apply a scanl1 (*) to it:

takeWhile (/= 600851475143) [ x | x <- primes, 600851475143 `mod` x == 0]

Here we have to use /= ("not equal to") because the list comprehension won't generate values greater than 600851475143 anyway. scanl1 is the same as scanl, except that it takes its initial value from the head of the list instead of as an argument. This produces the list [71,59569,87625999]. What is the significance of this list? It's the result of multiplying together the factors of our number, from smallest to largest. So we can assume that the largest divisor of our number is the original number divided by the last item in this list. The final result:

problem3 = n `div` (last $ takeWhile (/= n) [ x | x <- primes, n `mod` x == 0]))
    where n = 600851475143

Here we introduce where, a useful construct that allows us to define local variables. It can be placed at the end of the line or on a new line with an indent. If you don't follow these rules, the compiler will throw an error. This is because Haskell, unlike Perl or C++, is a "2D" language. The compiler can't just check for semicolons to determine where a line ends, so there are formatting rules that must be followed instead.
This version runs much faster, but you may have noticed that it cheats a bit. Since it only captures each divisor once, this method will fail on numbers whose prime factorization contains any repeats (e.g. 12 = 2*2*3). This isn't the case for our number, but it doesn't feel right using this solution.
Before we construct a real solution, I suppose I should discuss a method of generating primes. Unsurprisingly, there are quite a few. In general, their efficiency is directly proportional to their complexity. We'll use a simple implementation here because it's fast enough for our purposes:

primes = sieve [2..] where
    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

This is a recursive approach, but there is no base case! How can that be? The reason we can get away with this is Haskell's lazy nature. Each iteration adds values to the list of primes, so the algorithm will just keep running until it generates as many primes as you asked for. Actually this makes a lot of sense: since we are generating an infinite list, it wouldn't make any sense for our generating function to terminate!
As you may have guessed from the function name, this is an implementation of the Sieve of Eratosthenes (actually, not quite. See this paper if you are interested in a genuine sieve algorithm). Each time we find a new prime, we can eliminate any multiples of that prime from our list of numbers to check. To see how this works, imagine how this algorithm would calculate the third prime number, 5. We start with the list [2..]. sieve (p:xs) means that sieve takes a single argument (a list), but we treat it as a value p appended to the rest of the list xs. This allows us to refer to these values independently, and without having to use head. Thus our list is split into p = 2 and xs = [3..]. We then state that the return value (our list of primes) is defined as p appended to a new sieve of some list comprehension of xs. We know that what p is, so we can safely say that primes!!0 == 2. The list comprehension simply filters out numbers that are divisible by p, so in this case, the result of the list comprehension is [3,5..]. We then run sieve on this list, and take its first value as our new p. Now we have identified the second prime as 3, and we run a new list comprehension to eliminate the multiples of 3. We don't need to worry about removing multiples of 2, because the list that was passed in already had the multiples of 2 taken out! After one more iteration, we have our answer.
Now we will construct a non-cheating solution, using the same approach we used with Perl. We simply divide our number by primes of increasing magnitude, and stop when the prime number we are dividing by exceeds the square root of the number. This lends itself to three cases:

   1. The current prime exceeds the square root of the number. This will be the last prime in our list, so this is the base case.
   2. The current prime divides the number. Add the prime to the list of divisors, divide the number by the prime, and calculate the factors of the result.
   3. The current prime does not divide the number. Try the next prime.

We can implement this algorithm almost verbatim in Haskell using a feature called guards. Guards are similar to the cases we used earlier, when we defined the Fibonacci sequence. Each guard defines a condition that the function input is checked against, and separate function definitions are used depending on which condition matches (note that conditions are checked in order, top to bottom). Here's the implementation:

problem3 = factor 600851475143 primes
    where
        factor n (p:ps) 
            | p * p > n      = [n]
            | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
            | otherwise      = factor n ps

It's a bit lengthy, but it's (relatively) easy to understand and it does the job well. Though I enjoyed dealing with obfuscation in Perl, I find Haskell difficult enough to understand when it's written as plainly as this!

As promised, today we'll be moving on to Euler problem 2. To solve it, we'll have to write an implementation of the Fibonacci sequence. The full problem description follows.

Problem 2:
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

One of the cool things about Haskell is that it is lazily evaluated. This means that it won't try to calculate a value until you specifically ask for it. One neat benefit of this is that it allows us to construct infinite ranges, since the list isn't stored in memory until we reference it! This is useful for Euler problems, since they often involve infinite sequences.
There are multiple ways to construct the Fibonacci sequence in Haskell, so let's examine a few. We know that a Fibonacci number can be found by summing the previous two numbers, and we know that the first two numbers are 0 and 1. So we can easily define a function using these facts:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

It's neat that we can define "special cases" for our functions in this way. In Perl (and most imperative languages), we would have to write a statement like, "if the input is x, then return y." I prefer the Haskell approach because it gives these special cases a sort of mathematical gravitas; we define the first Fibonacci number to be 0.
Anyway, we can use this function to construct an infinite sequence using map:

fibs = map fib [1..]

map does what you would expect: it maps a function onto a set of values. Also note that we define infinite ranges by omitting their upper bound.
Of course, it would be nice if we could skip the function definition and just construct the sequence from scratch. One way to do this is with the scanl function. scanl takes a function, an initial value, and a list as arguments. It first applies the function to the initial value and the first value of the list. This result then replaces the initial value, and the process repeats. Each result is placed into a new list, which is the return value (note that the first element of this list will always be the initial value). This function is perfect for constructing the Fibonacci sequence; it's almost like they were made for each other! Here's the implementation:

fibs = 0 : scanl (+) 1 fibs

Here we use the : operator to tack on a 0 at the start of the list. Thus, to calculate fibs!!2 (this is how lists are accessed, by the way -- hence the title), we scanl over the initial list (which just contains 0) to get [1,1] and add 0 to the beginning to get [0,1,1]. To calculate fibs!!3, we scanl over the list [0,1,1] and append to get [0,1,1,2,3].
Another way of generating the Fibonacci series is to use zipWith, which "zips" two functions together with some specified function. I won't get into the specifics, but you can see for yourself how it works:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- Example:
--     [0,1,1,2,3,5]   (the original sequence)
--   + [1,1,2,3,5]     (this is the "tail")
--   = [1,2,3,5,8]     (result of zipWith)
--     [0,1,1,2,3,5,8] (append 0 and 1 to get the new sequence)

Why are we generating this sequence again? Right, to solve the Euler problem. Now that we have the sequence, we can write a simple list comprehension to perform the necessary computation. Our criteria in this case are that the values of x must even and less than 4 million. As before, we can easily sum the result of the list comprehension to get our answer:

problem2 = sum [ x | x <- takeWhile (<= 4000000) fibs, even x]

Note that we use takeWhile instead of x <= 4000000; we can't simply draw our values from fibs, since it is infinite, and a list comprehension must (by definition) evaluate every element of the list.
Phew! That was rather exhausting. It makes sense that we have to work hard to understand Haskell code, since it is radically different from "normal" (imperative) languages. The upside is that it can be much more concise and elegant!

Back from another hiatus. Winter break has come at long last, so I have some free time. After a few weeks of relaxing, I couldn't stand doing nothing any longer, so I decided to learn Haskell. It's completely different from the other languages I've programmed in; Perl, C++, and BASIC are all imperative languages, while Haskell is a functional language. I suspect it will be a while before I fully comprehend what it means for a language to be functional. Anyway, here's some music; let's get to know Haskell the same way we got to know Perl: Project Euler!


If you recall, Euler problem 1 asks that we find the sum of all numbers under 1000 that are divisible by 3 or 5. In Haskell, we'll be solving a lot of these types of problems using list comprehensions. A list comprehension is essentially a way of narrowing down a broad range of values, using some specific criteria.
Here, our range is the numbers 1 to 1000. We can use the syntax 1..1000 to represent this range, just as we did in Perl. Our criterion is the expression:
x `mod` 3 == 0 || x `mod` 5 == 0. The graves around mod signify that we are using it as an infix function; normally, a function is followed by its arguments, i.e. mod x 3. In mathematics (and Perl, with %), however, we use the syntax x mod 3. So the infix operator simply allows us to emulate this syntax and make the statement a bit more readable.
The final code for our list comprehension looks like this:

[x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

The output of a list comprehension is, unsurprisingly, a list. The initial x | means "the values of the resulting list will be x, where...", and the x <- [1..999] means we are drawing potential values of x from the range 1 to 999. Following that are the criteria that x must satisfy. Note that we could also have written:

[ if x `mod` 3 == 0 || x `mod` 5 == 0 then x else 0 | x <- [1..999]]

Haskell, like most functional languages, excels at manipulating lists. You might say that lists are to Haskell what strings are to Perl! Fortunately, most of the Euler problems involve sequences (i.e. lists) in some way, so Haskell is a good choice for solving them.
At any rate, we still have to sum up all the values of the resulting list. This is easily accomplished with the sum function (oh how I have longed for such a function in Perl...). We simply apply sum to our list comprehension and we have our answer:

problem1 = sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

I think I'll stop there for today, since problem 2 involves the Fibonacci sequence, which has a neat (but perhaps confusing) Haskell implementation.

EDIT: While list comprehensions are cool, they aren't exactly very "functional;" the preferred way to do things (especially things as simple as this) is to use filter:

problem1 = sum $ filter (threeOrFive) [1..999] where
    threeOrFive x = x `mod` 3 == 0 || x `mod` 3 == 0

Sorry folks, I know it's been a while. I've been busy installing Gentoo and settling into college. Anyway, let's look at some more Project Euler problems.

Problem 3:
What is the largest prime factor of the number 600,851,475,143?

The easiest (and therefore, worst) way to go about this would be to systematically test each number between 1 and 600,851,475,143 to see if it was a divisor, then check each divisor to see if it was prime, then return the largest of those. But aha! We don't need to check all the numbers, just the ones that are less than the square root of 600,851,475,143! So we really only need to test 775,147 numbers. We also know that primes can't be even, so we can start our loop index at 3 and increment by 2 each time instead of 1.

sub problem3 {
    for ($i = 3; $i < 775_147; $i += 2) {
        if (600_851_475_143 % $i == 0) and (# $i is prime) {
            $max = $i if ($i > $max);
        }
    }
    return $max;
}

Note that Perl lets you to add underscores anywhere you want in a number. Many people use them as replacements for commas.
Unfortunately, as you might have noticed, we don't really have a good way of checking to see if $i is prime. We could check all the numbers less than $i to see if they were divisors, but that would just add to the woeful inefficiency of this function. Instead, let's skip ahead to the good solution.

The good solution, it turns out, doesn't use a drastically different approach. There's only one crucial change: each time we find a divisor, we divide by it. Not only does this speed up the process by reducing the numbers we must check, it also guarantees that we'll only be finding prime factors, and that the last divisor we find will be the largest prime factor.

sub problem3 {
    $a = 600_851_475_143; $b = 3;
    while ($b != $a) {
        if ($a % $b == 0) {
            $a /= $b;
        else {
            $b += 2;
        }
    }
    return $a;
}

Of course, this can be greatly shortened by using a conditional and reverse loop structure:

sub problem3 {
    $a = 600_851_475_143; $b = 3;
    ($a % $b == 0) ? ($a /= $b) : ($b += 2) while ($b != $a);
    return $a;
}

On my i5 Gentoo machine, this code returned the correct answer in 0.002s. Much faster than the other method.

Next problem:

Problem 4:
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

This problem is harder than it looks, and you'll see why in a bit. The first thing we should do is find a way to check if a number is palindromic. Initially, I tried converting the number to an array and comparing each element to its mirror. But it turns out there's a much easier way: reverse operates just fine on a number, so it can be used to quickly find palindromes. Our first attempt might look something like this:

sub problem4 {
    for ($a = 999; $a > 100; $a--) {
        for ($b = 999; $b > 100; $b--) {
            return $a * $b if ($a * $b == reverse $a * $b);
        }
    }
}

Which will return 580085. However, Project Euler will tell you that this is the wrong answer! How could that be?
Well, what are the 3-digit numbers factors of 580005? Adding some print statements to the loop reveals that they are 995 and 583. 583 is suspiciously small, so that should be an indication of what went wrong. The problem is that we are decrementing $b much faster than $a. So it turns out that there is a palindromic number whose divisors fall between 995 and 583, producing a greater result overall. To find this number, we have to calculate all the palindromic numbers to find biggest one. This is easily accomplished in Perl:

sub problem4 {
    for $a (reverse 100..999) {
        for $b (reverse 100..$a) {
            if ($a * $b == reverse $a * $b) {
                $max = $a * $b if ($a * $b > $max);
            }
        }
    }
    return $max;
} 

Also note that the for loops have been cleaned up -- although the ..? operator can't be used to decrement, adding a reverse will produce the same effect. The right bound of the second loop has also been changed, since it's unnecessary to check numbers higher than $a.
This new approach returns the correct answer, though it takes more time than I'd like. We can make it run faster by upping the lower bound from 100 to 900, but that seems like cheating to me; it doesn't respect the spirit of the problem.

Good news, everyone! My code formatting woes are over. I fixed the funkiness with pre, so I can use that instead of h2 now. pre is nice because it preserves spaces (before, I was using the space character code instead -- it was hideous). I should also be able to extend code past the page margins now. The only downside of all this is that I have to go back and reformat all my old posts now. A small price to pay, all considered.

Anyways, today's subject is Project Euler, which is a series of mathematical problems that can be solved with code. They get pretty hard, so I haven't done a whole lot of them yet. Here's the first one:

Problem 1:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Pretty simple, as would be expected of any "Problem 1." Here's the braindead solution:

sub problem1 {
    $total = 0;
    for (1..999) {
        if ($_ % 3 == 0 or $_ % 5 == 0) {
            $total += $_;
        }
    }
    return $total;
}

Of course, it's appalling to me that this much code is required for such a simple task. So let's golf it down a bit. As you might expect, the if statement can be reduced to a conditional. The definition of $total is also unnecessary, because variables are initialized to zero by default.

sub problem1 {
    $x += ($_ % 3 == 0 or $_ % 5 == 0) ? $_ : 0 for (1..999);
    return $x;
}

The return statement could be replaced with a simple $x, but I'm not really shooting for the lowest character count here. It's just fun to tweak the functional aspects of the code.
Let's do one more:

Problem 2:
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

You'll find that lots of Project Euler problems deal with large sets of data. This is probably to make it impractical to solve the problems by hand (though to my knowledge, all the problems can be solved manually, given enough time).
Here's my solution:

sub problem2 {
    @fib = (1,1);
    push @fib, $fib[-1] + $fib[-2] for (1..31);
    $x += ($_ % 2) ? 0 : $_ for (@fib);
    return $x;
}

Here we see $_ % 2 being used as a conditional, because zero is false and non-zero is true. Note that this trick could be used in problem 1 as well, but or would have to be changed to and.
This could could definitely used some improvement. The first for loop is a bit of a cheat; I simply used the fact that past 31, the values of the series are greater than four million. It also seems lame to use two for loops when one could probably suffice.
The clever way of doing this problem lies in generating Fibonacci numbers. First, we can observe that only every third Fibonacci number is even. Additionally, the ratio between adjacent numbers is approximately ϕ = 1.618..., or phi. So we can generate even Fibonacci numbers by multiplying the last number by ϕ³. I found that 7 significant figures are enough to ensure accuracy.

sub problem2 {
    for ($i = 2; $i < 4_000_000; $i = int $i * 4.236068 + 0.5) {$x += $i}
    return $x;
}

It's necessary to round the result of the multiplication, since all numbers in the sequence are integers. Unfortunately, Perl does not have a proper rounding function, only a pseudo-floor function. So we add 0.5 to the result and chop off everything after the decimal point to get the rounded result. Much better, don't you think?

I'll be posting more Project Euler problems as I complete them. Happy coding!