apfelmus apfelmus at quantentunnel.de
Mon Jul 23 04:49:03 EDT 2007

```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

```