4
\$\begingroup\$

I'm playing with Haskell's list comprehensions, tuples, and foldr.

The exercise I've given myself is to find all triangles with a perimeter of length 26 in the set of triangles whose edges range from 1 to 10 in length.

main = do
  print triangles

triangles = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], hasPerimeterOf 26 (a,b,c)]

-- Determines whether a triangle has a perimeter of targetPerimeter
hasPerimeterOf targetPerimeter triangle = targetPerimeter == perimeter triangle

-- Calculates the perimeter of a triangle
perimeter triangle = foldr (+) 0 (toList(triangle))

-- Converts a tuple of three to a list
toList (a,b,c) = a : b : c : []

Is there a nicer way to convert a homogenous tuple to a list?

Generally, are there ways to simplify this code?

\$\endgroup\$
1
  • \$\begingroup\$ a few notes: 1) you can write a list directly in the comprehension like [ [a,b,c] | ...; 2) for such triangle problems it's usually faster to introduce a rule like a >= b >= c - and afterwards produce all permutations if needed. 3) as the formula is simple enough you might as well write let c = perimeter - a - b in the comprehension. Though the problem is simple enough so you won't need any optimizations. \$\endgroup\$ – bdecaf Mar 21 '16 at 10:33
5
\$\begingroup\$

The sum of length of any two sides of a triangle must be bigger then the length of the third side. Therefore there is no need to calculate hasPerimeterOf for all combinations of a, b and c. You can simplify it by adding another filter:

triangles = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], c < a + b, hasPerimeterOf 26 (a,b,c)]

Generally, are there ways to simplify this code?

I would simply use pattern matching on the tuple in perimeter like this:

perimeter (a,b,c) = a + b + c

hasPerimeterOf seems redundant here, anyway. Why not simply compare the perimeter with the desired value? It will be very readable and concise that way. The final code:

main = do
   print triangles

triangles = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], trianglePerimeter (a,b,c) == 26]

trianglePerimeter (a,b,c) = a + b + c

Note that I replaced the comment with a more meaningful function name.

EDIT:

As 200_success rightfully pointed out in the comment, the c < a + b filter leads to awkward results, because it removes some duplicate triangles, leaving other duplicates untouched. In my opinion, if triangles (1,2,4) and (2,4,1) are the same, then the final result should contain only one triangle for each unique set of sides. Otherwise, the mentioned filter has to be removed.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Checking that the triangles are valid is a good idea in general, but it happens that with side lengths up to 10 and a perimeter of 26, there would be no invalid triangles. Implementing the check as c < a + b is weird, though. It restricts c to be a short side, but doesn't deduplicate all permutations. For example, we get (10, 9, 7) and (9, 10, 7), but not (7, 9, 10), (7, 10, 9), (9, 7, 10), or (10, 7, 9). \$\endgroup\$ – 200_success Mar 20 '16 at 22:42
  • \$\begingroup\$ @200_success Thanks for the comment. I haven't though of deduplication... I will correct my answer tomorrow. \$\endgroup\$ – Kapol Mar 20 '16 at 23:29
4
\$\begingroup\$

I suggest you write your functions with more parameters, to allow easier changes:

triangles maxSide expectedPerimeter = 
  [(a,b,c) | a <- [1..maxSide], b <- [1..maxSide], c <- [1..maxSide], trianglePerimeter (a,b,c) == expectedPerimeter]

main = print $ triangles 10 26

Also, now re-using the function for different sides and perimeter values is possible, and testing is easier by using smaller values for the parameters.

\$\endgroup\$
1
\$\begingroup\$

Progressively inlining the functional definitions,

hasPerimeterOf targetPerimeter triangle = targetPerimeter == perimeter triangle
perimeter triangle = foldr (+) 0 (toList(triangle))
toList (a,b,c) = a : b : c : []

we get

triangles = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], hasPerimeterOf 26(a,b,c)]
 = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], 26 == perimeter  (a,b,c)]
 = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], 26 == foldr (+) 0 (toList(a,b,c))]
 = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], 26 == foldr (+) 0 [a,b,c]]
 = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], 26 == a+b+c]

because foldr (+) z [a,b,...,n] == a+(b+(...+(n+z)...)).

For uniqueness, we can generate only such triangles (a,b,c) that a ≤ b ≤ c in the first place:

 = [(a,b,c) | a <- [1..10], b <- [a..10], c <- [b..10], 26 == a+b+c]
\$\endgroup\$

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.