12
\$\begingroup\$

This is taken from HackerRank, which I hope is okay.

I've been playing around with Haskell and I haven't really been able to find anything that really goes beyond toy examples in terms of how to write a readable, well-structured program. Several parts of this seem messy but I guess I don't really know any better. Anyway, here's my code, which works (or at least passes all the unit tests supplied at HackerRank).

import Control.Monad

-- Given a list, return the pairs of consecutive elements in the list
consec :: [a] -> [(a,a)]
consec xs = zip xs (drop 1 (cycle xs))

-- Given a list of two elements, return a 2-tuple of the elements
make2Tuple :: [a] -> (a, a)
make2Tuple [x, y] = (x, y)

-- Apply a given function to the first element of a list
applyToFirst :: (a -> a) -> [a] -> [a]
applyToFirst _ [] = []
applyToFirst f (x:xs) = (f x):xs

-- Split a list at a specified delimiter
split :: Eq a => a -> [a] -> [[a]]
split _ [] = [[]]
split y (x:xs)
  | (x == y) = []:(split y xs)
  | (x /= y) = applyToFirst (x:) (split y xs)

-- Convert a string to a list of integers
stringToInts :: [Char] -> [Int]
stringToInts = map (read :: [Char] -> Int) . (split ' ')

-- Action that reads in a 2-tuple of integers
getInt2Tuple :: IO (Int, Int)
getInt2Tuple = fmap (make2Tuple . stringToInts) getLine

euclideanDistance :: ((Int, Int), (Int, Int)) -> Double
euclideanDistance ((x1, y1), (x2, y2)) = sqrt(fromIntegral((y2-y1)*(y2-y1) + (x2-x1)*(x2-x1)))

computePerimeter :: [(Int, Int)] -> Double
computePerimeter xs = sum (map euclideanDistance (consec xs))

main :: IO ()
main = (fmap computePerimeter (fmap (read :: [Char] -> Int) getLine >>= (\n -> replicateM n getInt2Tuple))) >>= print

Sample input

4
(0, 0)
(0, 1)
(1, 1)
(1, 0)

Sample output

4

Explanation

The input says that this polygon has four vertices, and then lists the vertices of a unit square. The perimeter of a unit square is 4 (one unit per edge times four edges), which is what's output.

\$\endgroup\$
7
\$\begingroup\$

consec will wrap around and pair the last element of your list as consecutive with the first. This isn't documented in the comment and IMO a little bit problematic. While it lends itself well to the problem you're solving, I'd try to change the implementation of consec a little and being explicit about the cycle property in the name.

Consider:

consec :: [a] -> [(a,a)]
consec [] = []
consec [x] = []
consec (x:xs@(y:_)) = (x,y):consec xs

This implementation has the benefit of being more explicit over zip xs (drop 1 $ cycle xs). It can be trivially extended to a consecCycle like so:

consecCycle :: [a] -> [(a,a)]
consecCycle [] = []
consecCycle [y] = []
consecCycle xs@(x:_) = consec (xs ++ [x])

For what it's worth, this is basically a stylistic call. I'm more prone to overspecifying my functions, avoiding pointfree style. I guess I just dislike oneliners...


make2Tuple is a dangerous one. You're explicitly forcing the function to be called with a list of only two elements by accepting a runtime error of "Non-exhaustive patterns in function make2Tuple".

I'd consider this bad practice. To totally define the function you could consider using a Maybe like so:

make2Tuple :: [a] -> Maybe (a,a)
make2Tuple [x,y] = Just (x,y)
make2Tuple _ = Nothing

this instantly communicates that the function is not totally defined and it avoids a runtime error.


applyToFirst is cleanly written and it clearly communicates intent. Yet I dislike the function because you're using it as a helper for something that's cleaner to implement without it.

split is a weird name for that function, I'd instead use splitWhere or splitIf and supply a predicate, which leads to the following typesignature:

splitWhere :: (a -> Bool) -> [a] -> [[a]]

which can then be implemented as follows:

splitWhere :: (a -> Bool) -> [a] -> [[a]]
splitWhere _ [] = [[]]
splitWhere p ls = go [] ls
    where 
        go accum (x:xs) = if p x then accum:go [x] xs else go (accum++[x]) xs
        go accum [] = [accum]

The advantage of this implementation is in the use of an "accumulator" instead of the applyToFirst you're using to achieve the same functionality.

It's also a tad easier to grasp, IMO, but YMMV


stringToInts is map read . words. Note that without an explicit type-signature GHCI can not infer the correct type, since read is not specified out enough.

Unfortunately this makes the work put into applyToFirst and split unnecessary :(


I'd simplify euclideanDistance's pattern by splitting up the tuple of tuples into separate parameters. To keep in line with how it's invoked you can then adjust computePerimeter to uncurry it like so:

computePerimeter xs = sum $ map (uncurry euclideanDistance) (consec xs)

Finally I find it hard to keep track of how your main works. It's probably easier to rewrite this as a do like so:

main = do
    vertices <- getLine
    polygon <- replicateM (read vertices) getInt2Tuple
    print $ computePerimeter (map fromJust $ filter isJust polygon)

This is IMO significantly easier to follow than your oneliner (and it also avoids all the fmap

Zeta noted that the last line can be shortened (and secured a bit) to:

print $ computePerimeter $ catMaybes polygon

Note that I've added the following imports and changed the getInt2Tuple signature to be an IO (Maybe (Int, Int)) instead:

import Control.Monad(replicateM)
import Data.Maybe(fromJust, isJust)
\$\endgroup\$
  • 1
    \$\begingroup\$ consec xs = zip xs (drop 1 xs) has the same effect and doesn't use explicit recursion. I get cycle confusion, but zip is a standard technique on HackerRank or other similar sites. \$\endgroup\$ – Zeta Nov 5 '17 at 15:04
  • 1
    \$\begingroup\$ "this instantly communicates that the function is not totally defined and it avoids a runtime error." That might be a little bit misleading. The function is totally defined when you use Maybe, it's just that for most of the domain Nothing will get returned. \$\endgroup\$ – Zeta Nov 5 '17 at 15:07
  • \$\begingroup\$ ad 1) duh. obvious in hindsight :) ad 2) Yes, so? I mean that's the whole idea of introducing the maybe there. Otherwise we'd just leave it partially defined and embrace the Exception.. \$\endgroup\$ – Vogel612 Nov 5 '17 at 15:09
  • 1
    \$\begingroup\$ A function f :: A -> B that does not return bottom for any input of type A (excluding bottom) is total, regardless of the used B. Your variant of make2Tuple is total, even though it uses Maybe. It's just a little wording issue at that point. The term partial doesn't apply to your variant. \$\endgroup\$ – Zeta Nov 5 '17 at 15:11
  • \$\begingroup\$ map fromJust . filter isJust is catMaybes (from Data.Maybe) \$\endgroup\$ – Zeta Nov 5 '17 at 15:15
1
\$\begingroup\$

I am chipping in my 2 cents.

I am at a similar stage as you: learning to write well-structured programs, especially when I/O is involved. I found your post when looking for suitable tasks.

I wrote my own solution to the task and noticed a few things.

  • This problem has a very linear flow and can (not should) be structured at the highest level in UNIX pipe-style; see main below.
  • The perimeter can (not should) be calculated as a fold by using a pair as the accumulator value; see function perimeter below. The initial value of the accumulator is (0, l) where l is the last point of the polygon. This wraps up nicely the points in a cyclic manner. Alternatively, you could do a foldr with the first point in the initial value of the accumulator.

Thanks for pointing out this nice exercise!

import Data.List
import Control.Monad

main :: IO ()
main = getN >>= getPoints >>= putPerimeter

-- get the number of points
getN :: IO Int
getN = readLn

-- get the points
getPoints :: Int -> IO [(Int, Int)]
getPoints n = replicateM n getPair
  where
    getPair :: IO (Int, Int)
    getPair = takePair . ints <$> getLine
      where
        -- ints of string as list
        ints :: String -> [Int] 
        ints xs = (read :: String -> Int) <$> words xs
        -- first two elements as pair (partial, I know)
        takePair :: [Int] -> (Int, Int) 
        takePair (x:y:_) = (x, y)

-- calculate and put the perimeter
putPerimeter :: [(Int, Int)] -> IO ()
putPerimeter = print . perimeter
  where
    -- perimeter of polygon, assuming edge from last to first
    perimeter :: [(Int, Int)] -> Double 
    perimeter pts = fst $ foldl' accPerim (0, last pts) pts
      where
        accPerim (perim, prevPt) curPt = (perim + dist prevPt curPt, curPt)
    -- Euclidean distance between points
    dist :: (Int, Int) -> (Int, Int) -> Double 
    dist (px, py) (qx, qy) = sqrt . fromIntegral $ (px - qx)^2 + (py - qy)^2
\$\endgroup\$
  • 1
    \$\begingroup\$ getN is readLn (restricted to Int), and getLine >>= pure . f can be written as fmap f getLine due to the monad/functor laws. \$\endgroup\$ – Zeta Nov 6 '17 at 18:39
  • \$\begingroup\$ sequence . replicate n is replicateM n from Control.Monad. \$\endgroup\$ – Zeta Nov 6 '17 at 18:40
  • 1
    \$\begingroup\$ I think you should focus a little bit more on the original code. You have presented an alternative solution, but have only slightly reviewed the original code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. You don't need to provide a single large block of working code. Instead, you can show how to refactor the original post's main into yours and so on. \$\endgroup\$ – Zeta Nov 6 '17 at 18:42
  • \$\begingroup\$ That's hard to see, but accPerim has a space leak, since it's not strict in perim, a defect that the cycle variant didn't have. That's hard to spot, though. Now that I've commented on your question: I think your code is eligible for a review on its own :). \$\endgroup\$ – Zeta Nov 6 '17 at 18:46
  • \$\begingroup\$ @Zeta. I know my contribution was not a full dollar but a meagre 2 cents: just a few quick notes on high-level structure and the possibility of a fold. Still, meant no harm, hopefully none done. I appreciate your comments. Haskell I/O is still... weird. Thanks! \$\endgroup\$ – user152712 Nov 7 '17 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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