2
\$\begingroup\$

I decided to dive into the world of functional programming since my programming so far has been mostly in C/C++, Java, and Python. I've gone through a couple Haskell tutorials and played around in GHCi so I decided to try my first real program. I decided to try one of the easier problems on Kattis.com, Transit Woes. You can get the full problem description here.

Essentially you are given a list of times that it takes to walk between bus stops, the transit times on the buses, and the intervals at which the buses come to the stops and you need to calculate the total travel time. It was really hard for me to get into a FP mindset, and I kept thinking how easy it would be if I could just write a for loop but I finally got it. I just wanted to get some advice on good FP coding practices, and what kinds of things I should stop doing or start doing so I can get into good habits from the beginning.

import System.IO
import Control.Monad

main = do
    lines <- replicateM 4 getLine
    let inputs = (map . map) read (map words lines) :: [[Integer]]
    let a = inputs !! 0 !! 0 + inputs !! 1 !! 0
    let b = zipWith (+) (tail $ inputs !! 1) (inputs !! 2)
    let c = inputs !! 3
    let finalTime = calcTime a b c
    putStrLn $ resultStr finalTime (inputs !! 0 !! 1)

calcTime :: Integer -> [Integer] -> [Integer] -> Integer
calcTime current travel intervals
        | length travel == 0 = current
        | otherwise = calcTime (firstStop + head travel) (tail travel) (tail intervals)
        where firstStop = head [n*i | n <- [1..], n*i >= current]
              i = head intervals

resultStr :: Integer -> Integer -> String
resultStr a b
        | a <= b = "yes"
        | otherwise = "no"
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Please add a description of what this Kattis is. For a variety of reasons, questions and answers on the Stack Exchange network should be self-contained. And so explaining the problem is required here. \$\endgroup\$
    – Peilonrayz
    Commented Apr 19, 2020 at 14:15
  • 1
    \$\begingroup\$ @Peilonrayz Thanks, I hadn't even thought about that being an issue. Updated the question to include a problem description \$\endgroup\$
    – Adam S
    Commented Apr 20, 2020 at 2:05

2 Answers 2

2
\$\begingroup\$

You have the right idea here by replacing an imperative loop with recursion.

The main improvement I would suggest is that in firstStop you are simulating waiting for the bus i minutes at a time instead of calculating how long to wait. The formula I came up with for that is (renaming i to interval as below):

where
  remainder = current `rem` interval
  firstStop =
    case remainder of
        0 -> remainder
        x -> interval - remainder

e.g. if we're at time 26 and interval = 5 then remainder is 1 and interval - remainder is 4 which correct since we need to wait until time 30. The exception is for when the wait time is 0, in which case interval - remainder would tell us 5 instead of 0, so I wrote out a case expression for that.


There are some Haskell practices you could do better. For example, head and tail are discouraged when you can use pattern matching instead. Here's one refactoring you could do:

calcTime :: Integer -> [Integer] -> [Integer] -> Integer
calcTime current [] intervals = current
calcTime current (travelTime:travelTimes) (interval:intervals) =
    calcTime (firstStop + travelTime) travelTimes intervals
        where firstStop = ...
\$\endgroup\$
1
\$\begingroup\$

I second @Steven's advice on using pattern matching.

Accessing list elements by index (!!) is discouraged because it has linear complexity and can raise unexpected errors if list is too short. For example:

let a = inputs !! 0 !! 0 + inputs !! 1 !! 0

is better written as

let (x:xs) : (y:ys) : _ = inputs
let a = x + y

here you check input format declaratively and can give semantic names to its parts.

Using this idea you can get rid of !! and tail in your code:

let [s, t, n]
      : (w : walkTimes)
      : rideTimes
      : intervals
      : _ = input

let a = s + w
let b = zipWith (+) walkTimes rideTimes
let c = intervals

It is more idiomatic to use predefined higher-order recursion combinators like fold instead of simple recursion. E.g. you can rewrite calcTime in terms of foldl. This will make it clear that you iterate over inputs only once and computing some kind of "running sum" of its elements.


Using length to check if list is empty is bad as it traverses whole list. Use travel == [] or null travel instead of length travel == 0.


main :: IO ()
main = do
    input <- map (map read . words) . lines <$> getContents
    let [s, t, n]
          : (w : walkTimes)
          : rideTimes
          : intervals
          : _ = input

    let b = zipWith (+) walkTimes rideTimes
    let finalTime = calcTime (s + w) $ zip b intervals
    putStrLn $ if finalTime  <= t then "yes" else "no"

calcTime :: Int -> [(Int, Int)] -> Int
calcTime = foldl (\c (t,i) -> t + i * (div c i + signum (mod c i)))
\$\endgroup\$
2
  • \$\begingroup\$ It looks like the expression (div c i + signum (mod c i)) is essentially a ceiling function on c / i. Is there an advantage to doing it that way as opposed to doing something like (ceiling $ (fromIntegral c) / (fromIntegral i))? It just took me a while to understand what yours was doing, and I think it's more obvious to use the ceiling function itself. Thanks for all your help! \$\endgroup\$
    – Adam S
    Commented Apr 29, 2020 at 22:46
  • \$\begingroup\$ Wow, that is embarrassing. It is really obvious now that this is ceiling. At the time I just mindlessly rewrote your code line by line without understanding the problem. \$\endgroup\$ Commented Apr 30, 2020 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.