Project Euler 8 - I don't understand it

Question

I looked up for a solution in Haskell for the 8th Euler problem, but I don't quite understand it.

import Data.List
import Data.Char

euler_8 = do
   str <- readFile "number.txt"
   print . maximum . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails . map (fromIntegral . digitToInt)
         . concat . lines $ str

Here is the link for the solution and here you can find the task.

Could anyone explain me the solution one by one?

Answer 1

If you're not familiar with the functions used, the first thing you should do is examine the types of each function. Since this is function composition, you apply from inside out (i.e. operations occur right to left, bottom to top when reading). We can walk through this line by line.

Starting from the last line, we'll first examine the types.

:t str
str :: String -- This is your input
:t lines
lines :: String -> [String] -- Turn a string into an array of strings splitting on new line
:t concat
concat :: [[a]] -> [a] -- Merge a list of lists into a single list (hint: type String = [Char])

Since type String = [Char] (so [String] is equivalent to [[Char]]), this line is converting the multi-line number into a single array of number characters. More precisely, it first creates an array of strings based on the full string. That is, one string per new line. It then merges all of these lines (now containing only number characters) into a single array of characters (or a single String).

The next line takes this new String as input. Again, let's observe the types:

:t digitToInt
digitToInt :: Char -> Int -- Convert a digit char to an int
:t fromIntegral
fromIntegral :: (Num b, Integral a) => a -> b -- Convert integral to num type
:t map
map :: (a -> b) -> [a] -> [b] -- Perform a function on each element of the array
:t tails
tails :: [a] -> [[a]] -- Returns all final segments of input (see: http://hackage.haskell.org/package/base-4.8.0.0/docs/Data-List.html#v:tails)
:t take
take :: Int -> [a] -> [a] -- Return the first n values of the list

If we apply these operations to our string current input, the first thing that happens is we map the composed function of (fromIntegral . digitToInt) over each character in our string. What this does is turn our string of digits into a list of number types. EDIT As pointed out below in the comments, the fromIntegral in this example is to prevent overflow on 32-bit integer types. Now that we have converted our string into actual numeric types, we start by running tails on this result. Since (by the problem statement) all values must be adjacent and we know that all of the integers are non-negative (by virtue of being places of a larger number), we take only the first 13 elements since we want to ensure our multiplication is groupings of 13 consecutive elements. How this works is difficult to understand without considering the next line.

So, let's do a quick experiment. After converting our string into numeric types, we now have a big list of lists. This is actually kind of hard to think about what we actually have here. For sake of understanding, the contents of the list are not very important. What is important is its size. So let's take a look at an artificial example:

(map length . take 13 . tails) [1..1000]
[1000,999,998,997,996,995,994,993,992,991,990,989,988]

You can see what we have here is a big list of 13 elements. Each element is a list of size 1000 (i.e. the full dataset) down to 988 in descending order. So this is what we currently have for input into the next line which is, arguably, the most difficult-- yet most important-- line to understand. Why understanding this is important should become clear as we walk through the next line.

:t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b -- Combine values into a single value
:t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] -- Generalization of zip
:t (:)
(:) :: a -> [a] -> [a] -- Cons operator. Add element to list
:t repeat
repeat :: a -> [a] -- Infinite list containing specified value

Remember how I mentioned we had a list of 13 elements before (of varying-sized lists)? This is important now. The line is going to iterate over that list and apply (zipWith (:)) to it. The (repeat []) is such that each time zipWith is called on a subsequence, it starts with an empty list as its base. This allows us to construct a list of lists containing our adjacent subsequences of length 13.

Finally, we get to the last line which is pretty easy. That said, we should still be mindful of our types

:t product
product :: Num a => [a] -> a -- Multiply all elements of a list together and return result
:t maximum
maximum :: Ord a => [a] -> a -- Return maximum element in the list

The first thing we do is map the product function over each subsequence. When this has completed we end up with a list of numeric types (hey, we finally don't have a list of lists anymore!). These values are the products of each subsequence. Finally, we apply the maximum function which returns only the largest element in the list.

Answer 2

EDIT: I found out later what the foldr expression was for. (See comments bellow my answer).

I think that this could be expressed in different way - You can simply add a guard at the end of the list.

My verbose version of that solution would be:

import Data.List
import Data.Char

euler_8 = do
    let len  = 13
    let str1 = "123456789\n123456789"
    -- Join lines 
    let str2 = concat (lines str1)
    -- Transform the list of characters into a list of numbers
    let lst1 = map (fromIntegral . digitToInt) str2
    -- EDIT: Add a guard at the end of list
    let lst2 = lst1 ++ [-1]
    -- Get all tails of the list of digits
    let lst3 = tails lst2
    -- Get first 13 digits from each tail
    let lst4 = map (take len) lst3
    -- Get a list of products
    let prod = map product lst4
    -- Find max product
    let m    = maximum prod
    print m

Answer 3

Reading the data

readFile reads the file "number.txt". If we put a small 16 digit number in a file called number.txt

7316
9698
8586
1254

Runing

euler_8 = do
   str <- readFile "number.txt"
   print $ str

Results in

"7316\n9698\n8586\n1254"

This string has extra newline characters in it. To remove them, the author splits the string into lines.

euler_8 = do
   str <- readFile "number.txt"
   print . lines $ str

The result no longer has any '\n' characters, but is a list of strings.

["7316","9698","8586","1254"]

To turn this into a single string, the strings are concatenated together.

euler_8 = do
   str <- readFile "number.txt"
   print . concat . lines $ str

The concatenated string is a list of characters instead of a list of numbers

"7316969885861254"

Each character is converted into an Int by digitToInt then converted into an Integer by fromInteger. On 32 bit hardware using a full-sized Integer is important since the product of 13 digits could be larger than 2^31-1. This conversion is mapped onto each item in the list.

euler_8 = do
   str <- readFile "number.txt"
   print . map (fromIntegral . digitToInt)
         . concat . lines $ str

The resulting list is full of Integers.

[7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4]

Subsequences

The author's next goal is to find all of the 13 digit runs in this list of integers. tails returns all of the sublists of a list, starting at any position and running till the end of the list.

euler_8 = do
   str <- readFile "number.txt"
   print . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

This results in 17 lists for our 16 digit example. (I've added formatting)

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
    [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
      [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
        [6,9,6,9,8,8,5,8,6,1,2,5,4],
          [9,6,9,8,8,5,8,6,1,2,5,4],
            [6,9,8,8,5,8,6,1,2,5,4],
              [9,8,8,5,8,6,1,2,5,4],
                [8,8,5,8,6,1,2,5,4],
                  [8,5,8,6,1,2,5,4],
                    [5,8,6,1,2,5,4],
                      [8,6,1,2,5,4],
                        [6,1,2,5,4],
                          [1,2,5,4],
                            [2,5,4],
                              [5,4],
                                [4],
                                 []
]

The author is going to pull a trick where we rearrange these lists to read off 13 digit long sub lists. If we look at these lists left-aligned instead of right-aligned we can see the sub sequences running down each column.

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,6,9,8,8,5,8,6,1,2,5,4],
  [9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,8,8,5,8,6,1,2,5,4],
  [9,8,8,5,8,6,1,2,5,4],
  [8,8,5,8,6,1,2,5,4],
  [8,5,8,6,1,2,5,4],
  [5,8,6,1,2,5,4],
  [8,6,1,2,5,4],
  [6,1,2,5,4],
  [1,2,5,4],
  [2,5,4],
  [5,4],
  [4],
  []
]

We only want these columns to be 13 digits long, so we only want to take the first 13 rows.

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,6,9,8,8,5,8,6,1,2,5,4],
  [9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,8,8,5,8,6,1,2,5,4],
  [9,8,8,5,8,6,1,2,5,4],
  [8,8,5,8,6,1,2,5,4],
  [8,5,8,6,1,2,5,4],
  [5,8,6,1,2,5,4],
  [8,6,1,2,5,4],
  [6,1,2,5,4],
  [1,2,5,4]
]

foldr (zipWith (:)) (repeat []) transposes a list of lists (explaining it belongs to perhaps another question). It discards the parts of the rows longer than the shortest row.

euler_8 = do
   str <- readFile "number.txt"
   print . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

We are now reading the sub-sequences across the lists as usual

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1],
  [3,1,6,9,6,9,8,8,5,8,6,1,2],
  [1,6,9,6,9,8,8,5,8,6,1,2,5],
  [6,9,6,9,8,8,5,8,6,1,2,5,4]
]

The problem

We find the product of each of the sub-sequences by mapping product on to them.

euler_8 = do
   str <- readFile "number.txt"
   print . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

This reduces the lists to a single number each

[940584960,268738560,447897600,1791590400]

From which we must find the maximum.

euler_8 = do
   str <- readFile "number.txt"
   print . maximum . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

The answer is

1791590400