> Consider the following Haskell-definition:
>
> nfib 0 = 1
> nfib 1 = 1
> nfib (n + 2) = nfib n + nfib (n + 1) + 1
>
>
> main = print (nfib 30)
>
>
> Execution of the (via hbc) compiled file
> results in 2692537 in 255 seconds.
>
>
> Changing the above definition like this:
>
> nfib 0 = 1
> nfib 1 = 1
> nfib n = nfib (n - 2) + nfib (n - 1) + 1
>
>
> main = print (nfib 30)
>
>
> results in 2692537 in 142 seconds.
>
> I think, that is not a desirable implementation
> of pattern-matching.
These are not equivalent definitions. The second is defined for
negative arguments, the first is not. Since (n+k) is intended
to match natural numbers (and not arbitrary integers), the following
is a closer definition (it's not equivalent, though, unless we're
talking about built-in data types, since no LAWS relate operations
such as (+), (-) and (>)).
> nfib 0 = 1
> nfib 1 = 1
> nfib n | n > 1 = nfib (n - 2) + nfib (n - 1) + 1
> To speed up my programs, therefore, I have to avoid (n+k)-patterns.
To speed up a program using arrays, switch off the bounds checks.
> In Miranda the definition using (n+2) is faster
For me it isn't. I'd be puzzled why it should be. After all, n+k
patterns must involve *some* extra tests.
To *really* speed up your program, use:
nfib :: Int -> Int
You are using an overloaded definition of nfib, which isn't compiled
as efficiently as a non-overloaded one by existing compilers. I think
you'll find that (n+k) patterns won't make such a big difference if
you use the non-overloaded form.
I couldn't be bothered to wait for overloaded nfib 30, so these are
nfib 25 timings (nfib 25 = 242785) on a lightly loaded SparcStation 1:
Non-Overloaded (plain): 2.0s
Non-Overloaded (n+k): 2.1s
Overloaded(plain): 42.8s
Overloaded(n+k): 76.5s
For the non-overloaded case, n+k patterns don't seem particularly
expensive.
Kevin
