Monday, March 31, 2014

Haskell : Unique right angle triangles without using Set operations (nub).

In GHCi, create a list of triangle values with tuples as below.
*Main> let triangles = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10] ] 
Now create a list of right angle triangles by
*Main> let rightAngleTriangle = [ (a,b,c)|(a,b,c) <- triangles , a^2 == b ^2 + c ^ 2]
Here variable a is hypotenuse. b and c are representing other 2 sides. Now call the function.
*Main> rightAngleTriangle
[(5,4,3),(5,3,4),(10,8,6),(10,6,8)]
The above result contains duplicate values. For a single hypotenuse value it printed twice. 2 Methods:

Method 1:

*Main> let rightAngleTriangle = [ (a,b,c)|(a,b,c) <- triangles , a > b, b > c,  a^2 == b ^2 + c ^ 2]

In the above example, I just added 2 conditions, a > b and b > c. That restricts the number of permutations.

Method 2:

*Main> let rightAngleTriangle2 = [(a,b,c) | a <- [1..10], b <- [1..a], c <- [1..b], a ^ 2 == b ^ 2 + c ^ 2] 

In the second example, we are taking a,b and c values separately instead of getting from a tuple. This also produces the same result.

Why not nub?

The nub is slower when we apply it in complex programs. The following one is the nub version.

*Main> import Data.List
*Main Data.List> nub rightAngleTriangle
[(5,4,3),(10,8,6)]
It is slow, because it works after the expression is evaluated. To confirm that, the following one produces duplicate values.
*Main Data.List> let rightAngleTriangle3 = nub [ (a,b,c)|(a,b,c) <- triangles , a^2 == b ^2 + c ^ 2]

*Main Data.List> rightAngleTriangle3
[(5,4,3),(5,3,4),(10,8,6),(10,6,8)]

So better to prevent the duplication at origin.

No comments:

Post a Comment