# Harshest critique for noob's code

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!

1 Like

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.

1 Like

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

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

I like that!

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

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.

1 Like

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)
``````