CODEWITHSUNDEEP
haskellfunctional-programminglist-comprehension
Jarmex
Jarmex

Reputation: 699

'unification' in list comprehensions

Ok, I'm attempting to make a function to determine if a list of tuples is transitive, i.e. if (x,y) and (y,z) is in the list, then (x,z) is also in the list.

For example, [(1,2), (2,3), (1,3)] is transitive.

Now, coming from a Prolog background, the following makes sense to me:

transitive xs = and [elem (x, z) xs | (x, y) <- xs , (y, z) <- xs ]

HOWEVER, it doesn't work. It appears that the 'y' does not get the single value as I would expect, but is 'reassigned' when it comes to the second tuple. Instead, we must use:

transitive xs = and [elem (x, z) xs | (x, y1) <- xs , (y2, z) <- xs, y1 == y2 ]

Why is this so? Why does the first example not cause an error, and doesn't this go against functional programming languages' principle of 'referential transparency?'

"However, in pure functional and logic languages, variables are bound to expressions and keep a single value during their entire lifetime due to the requirements of referential transparency." - Wikipedia

Thanks!

Upvotes: 6

Views: 234

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183873

Even in functional languages, there is name shadowing. Sometimes that is useful. In the first code, the (y,z) <- xs shadows the y bound by the (x,y) <- xs before.

Compile with warnings turned on to be alerted of such things.

Upvotes: 8

Related Questions