Advent of code: day 1

Question

I am learning Haskell, and what is better than advent of code to do so? The day 1 problem is about adding together the digits that are followed by the same digit from a "circular" string (the next of the last is the first). My solution is the following:

import Data.List
import Data.Char

result :: [Char] -> Int
result s = sum . map (digitToInt . fst)
               . filter (uncurry (==))
               . zip s
               $ (drop 1 . cycle $ s)

My question is not only about the algorithm (I think that it is ok, and the problem is not that difficult) but also about the "haskellish" style.

Because I am used to Rust/Ocaml/Elm etc., at first I wrote:

import Data.List
import Data.Char
import Data.Function

result :: [Char] -> Int
result str = str & zip (drop 1 . cycle $ str)
                 & filter (uncurry (==))
                 & map (digitToInt . fst)
                 & sum

then I read that Haskell people prefer to compose functions and then pass the parameter, not doing the forward thing. What do you think about that?

Also, I searched over the Internet, and I found some divided code, more like that:

import Data.List
import Data.Char

transformCharPairsToInts :: [(Char, Char)] -> [Int]
transformCharPairsToInts = map $ digitToInt . fst

keepPairsWithSameChars :: [(Char, Char)] -> [(Char, Char)]
keepPairsWithSameChars = filter $ uncurry (==)

result :: [Char] -> Int
result str = sum . transformCharPairsToInts . keepPairsWithSameChars $ zip str shiftedStr
  where
    shiftedStr = drop 1 . cycle $ str

What is the most idiomatic thing? The style that Haskell people prefer?

The main:

-- exemple cases
main = mapM_ (print . result) $ ["1122", "1111", "1234", "91212129"]

Thank you for your remarks.

Answer 1

You've used a common Haskell pattern here -- take a list, turn each element into a pair containing some extra information, process the "augmented" list, and strip off the extra information. Combining this pattern with point-free style, though, doesn't lead to particularly clean code because it's cluttered with constructs (like map (___ . fst) and filter (uncurry ___)) that aren't really part of the core algorithm but are still necessary to "interface" with your pair representation for the "augmented" elements.

I think you can get a more readable version by switching to list comprehension syntax, which let's you simultaneously simplify the higher-order function "sugar" (making map and filter implicit) and conveniently pattern match on the pairs (avoiding fst and uncurry), so you get something like this:

captcha :: String -> Int
captcha xs =
  sum [ digitToInt x | (x, y) <- zip xs (rotate xs), x == y ] 
  where rotate (x:xs) = xs ++ [x]

I think this is easier to puzzle through than the point-free version.

With respect to your specific questions about style, yes it's largely true that Haskell programmers tend to write chains of composed functions in right-to-left order of application:

foo . bar . baz $ xxx
foo $ bar $ baz $ xxx

rather than left-to-right:

xxx & (baz >>> bar >>> foo)
xxx & baz & bar & foo

On the other hand, chains of monadic or applicative actions are typically written in left to right order of action, and the styles are often mixed in the same code (e.g., monadic parsers written in applicative style), so I think Haskell programmers are used to seeing both styles.

Personally, I've found that writing a long chain of compositions in left-to-right order may make it easier to explain the algorithm in the comments:

result str 
    = str & zip (drop 1 . cycle $ str)  -- augment "d" w/ following digit
          & filter (uncurry (==))       -- keep "d" when followed by "d"
          & map (digitToInt . fst)      -- convert "d" to int
          & sum                         -- sum them all up

This particular example doesn't really benefit, but you can imagine other case where this step-by-step commenting style would be helpful.

As for using "divided code", as you call it, I think this can be quite helpful, but using very long variable names and elevating them to top-level definitions doesn't really do justice to the style. Also, pulling the filter and map into the helper function doesn't really aid readability, because those aren't the parts that are potentially hard to follow. Instead, I think something more like:

result' :: [Char] -> Int
result' str =
  sum $ map value $ filter equalPair $ zip str (rotate str)

  where
    value (x,_) = digitToInt x
    equalPair (x,y) = x == y
    rotate (x:xs) = xs ++ [x]

might be reasonable, though it's probably excessive in this small example.

Also, note that while point-free style is popular among many Haskell programmers, definitions like your:

transformCharPairsToInts = map $ digitToInt . fst
keepPairsWithSameChars = filter $ uncurry (==)

might more typically be written in pointed style:

transformCharPairsToInts = map (\(x,_) -> digitToInt x)
keepPairsWithSameChars = filter (\(x,y) -> x == y)

For example, if you browse through the source of Data.Foldable which is mostly pretty idiomatic, you'll see definitions like:

null = foldr (\_ _ -> False) True
length = foldl' (\c _ -> c+1) 0

rather than:

null = foldr ((const . const) False) True
length = foldl' (flip (const succ)) 0

Answer 2

Personally I'd prefer to write this as an explicit fold. IMO that's somewhat cleaner and significantly easier to grasp when skimming

result :: [Char] -> Int
result cs@(c:_) = go $ cs ++ [c]
  where
  go :: [Char] -> Int
  go (c1:chars@(c2:_)) = (if c1 == c2 then digitToInt(c1) else 0) + (go chars)
  go _ = 0
result = 0

This removes a lot of text that I consider pretty confusing to read.

Answer 3

Your original code looks OK for me. Far more readable at a glance than the divided code example.

I also tried to write my solution for day one in pointfree style (which is the style you are referring to). It may look nice most of the time, but sometimes it can also make code harder to understand.

My solution to convert the input string:

convert :: String -> [Int]
convert = map $ flip (-) 48 . ord

And to compute the result from the converted input:

getSum :: [Int] -> Int
getSum = sum . map match . pairs
  where
    pairs = zip <*> (drop 1 . cycle)
    match (a, b) | a == b    = a
                 | otherwise = 0