Functional Programming – How and Why

Re:Functional Programming – How and Why by cronin101 on Monday January 02, 2023 @09:31AM (#34218209)

Day 12 was a little hacky because of my foolhardy reluctance to ever use the obvious Dijkstra's Algorithm solution and always rolling my own organic recursive "flood fill" on the fly instead.

    -- ((start, end), heightMap)
    type Input = ((Coordinate, Coordinate), BoundedHeightMap)

    -- (length remaining, next coordinate)
    type DirectionsMap = M.Map Coordinate (Int, Coordinate)

I built up a map of "where to go next and how far left" and flood-filled it starting from the end and calculating for neighbours of those that just changed value for each step until convergence, which ended up being super useful for Part 2 since I got it "for free":

https://github.com/cronin101/AdventOfCode/blob/master/2022/D...

Day 13 on the other hand is something I'm far less ashamed of and really lets Haskell shine, it basically didn't need any code at all. I just defined how to parse an equivalent data representation, how it was sorted via Eq/Ord typeclass (following the brief), and used `compare` to do the lifting.

    instance Eq PacketData where
      (L l) == (P p) = P [L l] == P p
      (P p) == (L l) = L l == P p
      P p == P p' = p == p'
      L l == L l' = l == l'

    instance Ord PacketData where
      compare (L l) (P p) = compare (P [L l]) (P p)
      compare (P p) (L l) = compare (P p) (P [L l])
      compare (P p) (P p') = compare p p'
      compare (L l) (L l') = compare l l'

https://github.com/cronin101/AdventOfCode/blob/master/2022/D...

[ Parent | on HN ]

Re:Functional Programming – How and Why by Mathiciann on Monday January 02, 2023 @11:02AM (#34219362)

Thanks for sharing! Especially day 13 is really compact and elegant. Do I understand correctly that you define parser combinators to parse the packages? (I'm not really familiar with Haskell nor parser combinators)

For me the parsing was the hardest part when trying without mutable state so this helps a lot.

[ Parent | on HN ]

Re:Functional Programming – How and Why by cronin101 on Monday January 02, 2023 @01:34PM (#34221713)

Yup! Parser combinators are incredibly useful once you learn the basics well. They compose predictably and you can test the individual parts pretty succinctly (I usually use an inline eval'd comment in vscode to smoke test, as you can see) and allow you to build an arbitrarily complicated data structure at parse time.

I'll admit first few times were a bit of a headache learning the library (https://hackage.haskell.org/package/attoparsec-0.14.4/docs/D...) and idiomatic patterns, plus how to test/troubleshoot. But now Haskell is my go-to language for parsing and I can parse pretty much any AoC input into a suitable representation, with the forethought taking no longer than reading the brief, by composing parsers for the different parts of the input string into a larger parser.

Also, disclaimer, since I'm the only one reading my code I often make oneliner "pointfree" parsers using dense syntax/tricks (as a little extra mental puzzle) instead of vastly more readable "do notation", so don't let the special character soup put you off.

[ Parent | on HN ]