Aesthetics, vocabulary and the idiomatic

Learn
1

I picked Haskell up a couple weeks ago. I’m solving AoC2022 here and I’m comparing myself to Daniel Lin’s solutions because he seems to know what he is doing.

My Haskell vocabulary is much smaller than his, but my solutions have similar lines of code (LOC). To my mind: (1) less vocabulary used means more comprehensible, and (2) less LOC (given point 1) is preferable. So, some heuristic which minimises both vocabulary and LOC is what I assume best. However, I realise this could be naive when considering Haskell code.

Are my solutions worse than Daniel’s? Am I thinking about this wrong when it comes to Haskell?

2 Likes
2

Yes, I’d say that sounds right.

I only had a quick look but it seemed to me that you have very similar solutions. Is there a particular example that you think demonstrates the difference between your two styles?

2 Likes
3

From what I’m seeing Daniel Lin is using libraries like text and modules like Data.Bits (in day 3) to get better performance, which is one metric which you haven’t yet mentioned.

4

Sure, Day 1, 3, 5 and 7 are all good examples. Note the imports at the top. Daniel’s vocabulary (especially solution 5) is much larger.

1 Like
5

I should have added ceteris paribus in the original post somewhere :slight_smile: It isn’t obvious (to me) that performance considerations are driving vocabulary choice at least on the first 8 problems. Day 5 (Daniel, me) is an example.

6

I see — at least in Daniel’s solutions — less LOCs is achieved by omitting type signatures. I don’t like it.

7

In the day 5 solution of Daniel Lin, 3 out of the 8 imports are due to using Text instead of String, which is directly related to performance. And then using Data.Map instead of lists of tuples is also directly related to performance.

And there’s yet another metric you could take into account which is dependency footprint. The PCRE package uses a large foreign library under the hood. And lenses is also quite a heavy dependency. The packages that Daniel Lin depends on like text and containers are pretty much standard libraries in Haskell.

1 Like
8

On the other hand, I think the regex is much easier to understand than the handwritten parser (although I’d prefer to see the "moves", "from", and "to" tokens appear explicitly in the regex, and I find the implementation of moves hard to understand).

2 Likes
9

Yes, that’s a good point. It could be the case that he is minimising dependencies. Here are the dependencies from the cabal file:

        array ^>=0.5.4.0
      , base ^>=4.16.0.0
      , containers ^>=0.6.5.1
      , heap ^>=1.0.4
      , megaparsec ^>=9.3.0
      , mtl ^>=2.2.2
      , parallel ^>=3.2.2.0
      , primitive ^>=0.7.4.0
      , split ^>=0.2.3.5
      , template-haskell ^>=2.18.0.0
      , text ^>=2.0.0
      , vector ^>=0.13.0.0

I don’t know enough to say, but does it fit the dependency weight minimisation hypothesis?

I did a split/join thing first prior to using lens. I only put it in because the Internet said its all the rage :slight_smile: It would have added 2 LOC to the solution and the lens equivalent is prettier. If i don’t end up using lens more often, I’ll probably take it out.

Meanwhile regex, I was surprised it wasn’t in the standard library. I find it ubiquitously useful, however I note that often solvers will resort to “megaparsec” rather than regex, but I guess this is for the sake of practice rather than practicality. I did something very similar with DCGs in Prolog when completing AoC2023.

10

I think so, here is the full picture of all transitive dependencies (excluding boot libraries):

image
image2165×913 92.2 KB

So only 13 non-boot libraries and I think only vector and megaparsec are large libraries.

In contrast, this is what the dependency graph of an executable that only depends on the lens library looks like:

image
image1029×1225 236 KB

1 Like
11

That’s a scary looking graph :slight_smile: I’ll see if I lean on lens by the time I complete the whole thing. If I use it just here and there, I’ll take it out.

| hypothesis granted = I guess you’re saying that avoidance of dependencies in packages is causing Daniel to use a more diverse vocabulary, is that right? The implication isn’t obvious to me.

| otherwise = Why use vector and megaparsec if they are large libraries when trying to minimise dependencies? From AoC2023 experience, it is unlikely there is no other way and megaparsec usage starts very early in the solutions.

12

I think performance is an important consideration for Daniel as @jaror noted earlier. I noticed this for day 9, wherein he accommodates faster processing for 64-bit platforms. The wide and varied choice of functions may be driven by performance considerations.

13

By “vocabulary”, do you mean the number of different functions / imports used?

I’ve never really heard of the word “vocabulary” used to refer to the amount of an API that is known/used, although it does make sense in context. It does seem like an interesting idea to try to reduce the number of different functions used while keeping the same line count and providing the same functionality.

(It feels like it is at least vaguely related in some way to the Fairbairn Threshold)

14

Yeah exactly: functions and imports, but also fancier things (applicatives, arrows and all that).

I was surprised that whilst doing the Penn State course the author advocates rewriting a simple recursive function as a fold on count of it being more idiomatic even though it seems to makes the function longer:

fun2 :: Integer -> Integer
fun2 1 = 0
fun2 n | even n = n + fun2 (div n 2)
       | otherwise = fun2 (3 * n + 1)

versus

fun2' :: Integer -> Integer
fun2' =
  sum . filter even . takeWhile (/=1) . iterate choose
  where choose x | even x = div x 2
                 | otherwise = 3*x + 1

I supposed that’s what I’m asking. In my view, “describe the thing concisely in the most plain language possible” is what I aim for by default. That view also helps me situate where complexity is appropriate: it can’t be done otherwise or it significantly improves conciseness.

1 Like
15

Examples like this one are double-edged. On the one hand, the latter example (fun2') demonstrates the use of composable, reusable components, which is absolutely an important skill for software engineering in the large. But notice how the author has to intimately know the existing building blocks and come up with some clever solutions in order to make it work. It probably took 10 times longer to write, and will always take 5-10 times longer to understand it when reading it again. It also had to introduce a new name, which is dangerous. (What does “choose” mean? Is it really “choosing”? Naming things is indeed one of the hardest tasks in computer science!)

If you wrote a large system in the spiritual style of fun2', you will end up with a much more maintainable, understandable system: ideally, you’ll only ever be working in the guts of one particular component at a time, and thanks to its well-defined boundaries you’ll have a lot less to think about while working on it. The initial cost of designing good interfaces between components would pay off. But if you actually wrote fun2' in one of my projects, I would not accept it in a code review. :smiley:

3 Likes
16

In later exercises the course goes through some binary tree algorithms by first creating a treeFold function and then organising all the code around it so that the final call can be a treeFold. I.e.

-- WEEK 8

-- Ex. 2

treeFold :: (a -> [b] -> b) -> Tree a -> b
treeFold f (Node x xs) = f x $ map (treeFold f) xs

nextLevel :: Employee -> [(GuestList, GuestList)] -> (GuestList, GuestList)
nextLevel e@(Emp _ f) [] = (GL [e] f, GL [] 0) 
nextLevel e0@(Emp _ f0) xs0 =
  (glCons e0 $ mconcat $ map withBoss xs0, mconcat $ map (uncurry max) xs0)
  where
    withBoss (gl1@(GL xs f1), GL ys f2)
      | f1 - (sBF gl1) >= f2 = GL xs (f1 - (sBF gl1))
      | otherwise = GL ys f2
    sBF (GL ((Emp _ f):_) _) = f
    sBF _ = 0

maxFun :: Tree Employee -> GuestList
maxFun = uncurry max . treeFold  nextLevel

Ok, we’ve encapsulated a recursive pattern : treeFold, but is this code really clearer than what you’d get if you just wrote it as a recursion in the first place? This aesthetic is really not obvious to me.

17

Ok, we’ve encapsulated a recursive pattern : treeFold, but is this code really clearer than what you’d get if you just wrote it as a recursion in the first place? This aesthetic is really not obvious to me.

A famous paper about fold says the following:

Programs written using fold can be less readable than programs written using
explicit recursion

Representing your function using a fold makes it more amenable to analysis and composition, but nothing says that it will be more legible or understandable. So if one doesn’t need the extra flexibility, I guess the explicitly recursive version is perfectly ok.

I wonder how feasible would be to “recover” a function in fold form from an explicitly recursive version. Is there any language that does this?

18

Some total dependently typed languages, such as Epigram and Coq Equations, have to do this, because folds are the way they guarantee termination.

But of course total programming hasn’t really broken into the mainstream yet.

Also, why don’t you quote the whole sentence:

Programs written using fold can be less readable than programs written using explicit recursion, but can be constructed in a systematic manner, and are better suited to transformation and proof.

I think that highlights both the positive and negative aspects of folds. Especially the systematic construction is very useful for teaching.

1 Like
19

Well, this isn’t true in every case. Sometimes an idea is easier to learn using words from a small set, but other times having to use only words from a small set makes it harder to get the idea at the middle. The best way to write a thought will be different for different people who read it.

The fastest case for sending an idea is between two people who both know the same big set of words and can use them well. If you can expect someone else to know the same big set of words as you, it throws away time to use only the small set. Some of that time goes just to looking at a thing that is written in a different way and trying to see what it means!

But if you are learning, of course you have to start with a small set of words; and if you want to help someone who is learning you need to use the small set with them. That doesn’t mean that the small set is best, or what you should use for all time.

3 Likes
20

Not exactly what I meant. Check out these two AoC 2022 Day 10 solutions.

This one contains lots of vocab, language extensions, functors: chocolate sundae with sprinkles :slight_smile:

{-|
Module:         Day10
Description:    <https://adventofcode.com/2022/day/10 Day 10: Cathode-Ray Tube>
-}
{-# LANGUAGE OverloadedStrings, ViewPatterns #-}
module Day10 (day10a, day10b) where

import qualified Data.IntMap as IntMap (fromDistinctAscList, lookupLT)
import Data.Ix (inRange)
import Data.List (intercalate, unfoldr)
import Data.List.Split (chunksOf)
import Data.Maybe (mapMaybe)
import Data.Text (Text)
import qualified Data.Text as T (lines, stripPrefix)
import qualified Data.Text.Read as T (decimal, signed)

parse :: (Integral a) => Text -> [(Int, a)]
parse = scanl f (0, 1) . T.lines where
    f (i, x) "noop" = (i + 1, x)
    f (i, x) (T.stripPrefix "addx " -> Just (T.signed T.decimal -> Right (dx, ""))) = (i + 2, x + dx)

day10a :: Text -> Int
day10a input = sum . zipWith (*) taps . map snd $ mapMaybe (flip IntMap.lookupLT signals) taps where
    signals = IntMap.fromDistinctAscList $ parse input
    taps = [20, 60, 100, 140, 180, 220]

day10b :: Text -> String
day10b input = intercalate "\n" $ take 6 rows where
    sprites = concat $ unfoldr f (0, 1, parse input)
    f (i, x, (j, y):signals) = Just (replicate (j - i) x, (j, y, signals))
    f (_, x, _) = Just (repeat x, undefined)
    rows = zipWith draw [0..] <$> chunksOf 40 sprites
    draw i x = if inRange (-1, 1) $ x - i then '\x2593' else '\x2591'

This one imports printf. No fancy footwork, smaller vocabular: vanilla ice-cream :slight_smile:

#!/usr/bin/env runhaskell

import Text.Printf (printf)

parse :: [String] -> [(Int,Int)]
parse ls = zip (scanl (+) 1 [x | (x,_) <- ws]) (scanl (+) 1 [y | (_,y) <- ws])
  where ws = map (p' . words) ls
        p' ["addx",n] = (2,read n :: Int)
        p' _          = (1,0)

main :: IO ()
main = do
  str <- getContents --readFile "input.txt"
  let cmds  = parse (lines str)
      val n = snd $ last $ takeWhile ((<= n) . fst) cmds
      mx    = maximum $ map fst cmds
      part1 = sum [j * val j | j <- takeWhile (<= mx) [20,60..]]
      chk v = abs (mod (v-1) 40 - (val v)) <= 1
      xs    = map (\i-> if chk i then '#' else '.') [1..mx]
      grp   = takeWhile (/=[]) $ map (take 40) $ iterate (drop 40) xs
  printf "Part 1: %s, Part 2:\n\n" (show $ part1)
  mapM_ putStrLn $ grp

The vanilla here has considerably fewer lines of code than the chocolate sundae but solves the same problem. Ceteris paribus by default I prefer vanilla. But I’m starting to understand more why in the grand scheme the chocolate Sundae might be better.

What I implicitly understand from the commenters is that had the two authors written 10,000 lines of code each in their styles above, what appears more verbose and redundant in these small puzzles would have out-sized benefits.