CODEWITHSUNDEEP
haskell
MikeKlemin
MikeKlemin

Reputation: 959

Abs beginner Haskell pattern matching

I just managed to install Haskell and EclipseFP in the way that it all works under ubuntu! :) It took me really long to make it all work with no --force :) I starting explore learnyouahaskell and that pattern thing looks really fun... But I have question, for example I would like to calculate an equation like this:

equation :: [(Integer, Integer)]
equation = [ (x,y) | x <- [1..100],y<-[1..100], y == 2*x-4, x == 2*y-4]

I have to put limits on x and y ranges, but is it possible to use x<-[1..] and y<-[1..] and make the function stop after it finds first pair of x and y?

Upvotes: 3

Views: 217

Answers (2)

dfeuer
dfeuer

Reputation: 48611

We're looking at two equations here:

y = 2*x-4
x = 2*y-4

Substituting the first equation into the second,

x = 2*(2*x-4)-4

Expanding,

x = 4*x-12

So x = 4.

Substituting back in to the first equation, y = 4.

Thus the first and only solution is x = y = 4. You can solve this most simply in Haskell by defining

firstSolution = (4,4)

You can (and should) then write a HUnit test for the solution, to check that it really is a solution, and a QuickCheck property for the solution to check that it is the first one.

Upvotes: 1

chi
chi

Reputation: 116174

The problem with x <- [1..], y <- [1..] is that x=2 will be tried only after all the possible pairs (1,y) have been tried, for each y>=1. However, if no such pair matches your criterion, trying all such pairs requires an infinite amount of time. In that case, we never get to x=2 or any larger value for x.

What you need is a "fair" scheduler of all the pairs which does not get stuck on a strict subset of the cases. Mathematically, this is called a dovetailing function. This is essentially a bijective function from naturals to pairs of naturals. Or, if you prefer, it is a way of enumerating all the possible pairs: here's such an enumeration

(1,1) (2,1) (1,2) (3,1) (2,2) (1,3) (4,1) (3,2) (2,3) (1,4) ...

The trick is to list all the pairs having sum 2, then those having sum 3, and so on. In Haskell those pairs can be coded as

-- pair components start from 1 as in the OP's code
allPairs :: [(Integer, Integer)]
allPairs = [ (x,y) | s <- [2..] , x <- [1..s] , let y = s - x ]

Indeed, this chooses the sum s first (infinitely many choices here), and then proceeds to lists the (finitely many) pairs having that sum.

Once you have done this, your code simply becomes:

equation :: [(Integer, Integer)]
equation = [ (x,y) | (x,y) <- allPairs, y == 2*x-4, x == 2*y-4]

And, if you just want the first element

firstSolution :: Integer
firstSolution = head equation

That's it!

(Keep in mind that evaluating firstSolution may not terminate if no solution exists.)

Upvotes: 9

Related Questions