Mirko Rahn wrote:
apfelmus wrote:
Note that using Peano-numbers can achieve the same effect of stopping the length calculation as soon as more than one character is different.
data Nat = Zero | Succ Nat deriving (Eq, Ord)
instance Num Nat where (Succ x) + y = Succ (x+y) Zero + y = y
Very nice (and quite fast), thanks for sharing this.
One point: Writing down the equations for (+) by looking at the left argument first, you introduce an additional constraint to the user program, since if we have
lenL [] = 0 lenL (x:xs) = 1 + lenL xs
lenR [] = 0 lenR (x:xs) = lenR xs + 1
then
*FingerSpell> (lenL (repeat ()) :: Nat) < 10 False *FingerSpell> (lenR (repeat ()) :: Nat) < 10 *** Exception: stack overflow
So you can change a program that returns a proper value to one that loops by replacing lenL with lenR. Such problems are very difficult to track down, even if the library documentation states it very clearly.
It's the same with (||) or (&&): any p = foldr (||) False . map p any' p = foldr (flip (||)) False . map p Here, any' id will choke on x = True : repeat False but any id works just fine. Since there's no way to have a function be lazy in both arguments, the implicit convention is to make functions strict in the first arguments and, if applicable, lazy in the last arguments. In other words, the convention is True || _|_ = True but not _|_ || True = True 1 + _|_ = Succ _|_ but not _|_ + 1 = Succ _|_ Regards, apfelmus