[Haskell-cafe] Is "take" behaving correctly?

rahn at ira.uka.de rahn at ira.uka.de
Thu Sep 13 03:32:30 EDT 2007


>> pref_eq k xs ys = take k xs == take k ys

>> This seems to be a straightforward implementation with good properties.

> Actually, no, at least not if implemented naively.

I choosed this example, since I stumbled on this question last week.  
Reputable mathematicians doing "combinatorics on words" are using  
exactly this definition! (Karhumäki, Harju) There are others (Holub),  
that use the (to the computer scientist) nicer(?)

pref_eq 0 _  _          = True
pref_eq _ _  []         = False
pref_eq _ [] _          = False
pref_eq k (x:xs) (y:ys) = x == y && pref_eq (k-1) xs ys

And as you guess it, there are lemmata (and probably theorems), that  
hold for one of the definitions only... Later, the mathematicians  
agree upton to call the first version "pref_eq" and the second  
"pref_eq_proper".

And yes, you are right, just to change the behavior of take would not  
solve this issue. My topic was really more like

> "don't leap into coding a function before you know what it means"

as you pointed out with nice words :-) This is not the main topic of  
the thread (is this true?) but we are in a cafe, so from time to time  
one adds some cents...

/BR


More information about the Haskell-Cafe mailing list