Harshest critique for noob's code

[FedericoStra]

Hello, I’m new to the forum and I decided to start things off by letting you all throw tomatoes at me!

It’s been quite some time since I last used Haskell and I wanted to get back to it. As an exercise, I decided to solve this problem https://codeforces.com/problemset/problem/1552/F.

The point is not to discuss the actual solution, so here is a link to the Rust playground with a reference implementation which I tried to replicate in Haskell (it’s not quite a solution to the problem mentioned above, but rather a simplification). Here is the Haskell implementation about which I’d like to have a critique.

• Main.hs

module Main (main) where

import Lib

main :: IO ()
main = do
    let portals = [(4,1), (5,2), (7,3)]
    let len = journeyLength portals
    putStrLn $ show len

• Lib.hs

module Lib
    ( journeyLength
    ) where

import Data.Array

-- lowest index between `lo` and `hi` of an element not less than `x`
bisect :: (Ix i, Integral i, Ord e) => Array i e -> e -> (i, i) -> i
bisect a x (lo, hi)
    | lo == hi  = lo
    | otherwise = let mid = lo + div (hi - lo) 2 in
        if a!mid < x
        then bisect a x (mid + 1, hi)
        else bisect a x (lo, mid)

-- last element of an array
aLast :: Ix i => Array i e -> e
aLast a = a ! (snd $ bounds a)

journeyLength :: [(Int, Int)] -> Int
journeyLength portals = aLast entrances + 1 + aLast ps
  where
    entrances = listArray (1, length portals) (map fst portals)
    exits = listArray (1, length portals) (map snd portals)
    -- partial sums of the return times
    ps = array (0, length portals) ((0,0) :
        [(i, ps!(i-1) + rt)
            | i <- [1..length portals]
            -- first portal after the i-th exit
            -- `ps!i` is the sum of the return times of the portals `1..i`
            , let j = bisect entrances (exits!i) (1, i)
            -- return time
            , let rt = ps!(i-1) - ps!(j-1) + entrances!i - exits!i])

Some possible questions

• Is my code layout acceptable by common standards?
  • Is the indentation and whitespace decent enough?
  • Are line breaks where they are supposed to be?
    (For instance the if then else expression in bisect and the list comprehension in journeyJength)
• Is my usage of guards in bisect fine, or is there a better way to express it?
• Is the usage of let in in bisect fine, or should I prefer a where clause?
• Is there a better way to define ps, which is possibly more readable or better in some other regards?
• Should I refactor something?
• Is there anything else that catches the eye of an expert?

Basically, I’d like to have the harshest critique possible to see how this simple snippet would have been written more idiomatically by a Haskell guru.

Thanks!

[jaror]

The first thing that I notice is that you’re using the array package. Personally, I consider it practically deprecated in favour of vector.

I personally like to use fewer intermediate variables, e.g. in main I’d write:

main = print $ journeyLength [(4,1), (5,2), (7,3)]

bisect assumes the array is sorted: there should be a comment about that.

If you use a where clause in bisect you can make the guards prettier:

bisect a x (lo, hi)
    | lo == hi = lo
    | a ! mid < x = bisect a x (mid + 1, hi)
    | otherwise = bisect a x (lo, mid)
    where mid = lo + (hi - lo) `div` 2

You’ve got a redundant $ in aLast:

aLast a = a ! snd (bounds a)

(The linter hlint that comes with HLS gives this warning)

As for formatting, I think what ormolu (also included in HLS) produces is slightly nicer than what you have written:

module Lib (
  journeyLength,
) where

import Data.Array

-- lowest index between `lo` and `hi` of an element not less than `x`
bisect :: (Ix i, Integral i, Ord e) => Array i e -> e -> (i, i) -> i
bisect a x (lo, hi)
  | lo == hi = lo
  | a ! mid < x = bisect a x (mid + 1, hi)
  | otherwise = bisect a x (lo, mid)
  where
    mid = lo + div (hi - lo) 2

-- last element of an array
aLast :: Ix i => Array i e -> e
aLast a = a ! snd (bounds a)

journeyLength :: [(Int, Int)] -> Int
journeyLength portals = aLast entrances + 1 + aLast ps
  where
    entrances = listArray (1, length portals) (map fst portals)
    exits = listArray (1, length portals) (map snd portals)
    -- partial sums of the return times
    ps =
      array
        (0, length portals)
        ( (0, 0) :
            [ (i, ps ! (i - 1) + rt)
            | i <- [1 .. length portals]
            , -- first portal after the i-th exit
            -- `ps!i` is the sum of the return times of the portals `1..i`
            let j = bisect entrances (exits ! i) (1, i)
            , -- return time
            let rt = ps ! (i - 1) - ps ! (j - 1) + entrances ! i - exits ! i
            ]
        )

Although the commas in the list comprehension in journeyLength look odd.

Without understanding exactly what journeyLength is doing, I see an opportunity for improvement. I’d avoid indexing arrays as much as possible and instead get elements directly from the portals list:

journeyLength portals = aLast entrances + 1 + aLast ps
  where
    entrances = listArray (1, length portals) (map fst portals)
    -- partial sums of the return times
    ps =
      listArray
        (0, length portals)
        ( 0 :
            [ ps ! (i - 1) + rt
            | (i, (entry, exit)) <- zip [1 ..] portals
            -- first portal after the i-th exit
            -- `ps!i` is the sum of the return times of the portals `1..i`
            , let j = bisect entrances exit (1, i)
            -- return time
            , let rt = ps ! (i - 1) - ps ! (j - 1) + entry - exit
            ]
        )

Then you don’t even need the exits array.

[FedericoStra]

Thank you very much @jaror for the detailed commentary, it’s much appreciated!

@jaror

The first thing that I notice is that you’re using the array package. Personally, I consider it practically deprecated in favour of vector.

This sort of knowledge about the ecosystem is very insightful for newcomers.

@jaror

If you use a where clause in bisect you can make the guards prettier:

I like that!

@jaror

(The linter hlint that comes with HLS gives this warning)

As for formatting, I think what ormolu (also included in HLS) produces is slightly nicer than what you have written:

I haven’t set up HLS yet, and I didn’t know about ormolu, thanks for the reccommendation!

@jaror

Without understanding exactly what journeyLength is doing, I see an opportunity for improvement. I’d avoid indexing arrays as much as possible and instead get elements directly from the portals list:

Ah very nice! This matches even closer my more idiomatic implementation in Rust, which uses iterators instead of vectors. Before translating into Haskell I simplified it a bit and introduced more arrays along the way. It didn’t occur to me that I could use listArray for ps too.

---

Thanks a lot again! I’ll make sure to adopt HLS, hlint and ormolu to guide me in the future.

[gcox]

The solution you already got factored out the exits array altogether, which is great, but just as additional information: you could rewrite the definitions of entrances and exits in journeyLength to remove duplication using unzip and both, as follows. Hoogle is good for finding functions like these.

import Data.Tuple.Extra (both)

journeyLength portals = aLast entrances + 1 + aLast ps
  where
    (entrances, exits) = both toArray $ unzip portals
      where toArray = listArray (1, length portals)
         -- added toArray definition just to avoid a long line
    -- (no changes to the rest of the function)