Editing Talk:1312: Haskell
Please sign your posts with ~~~~ |
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 26: | Line 26: | ||
::::And here's one which is closer to what an Haskeller would write (if he ever needed to compute Fibonacci numbers and couldn't bother using one of the good (non-linear) algorithms) : | ::::And here's one which is closer to what an Haskeller would write (if he ever needed to compute Fibonacci numbers and couldn't bother using one of the good (non-linear) algorithms) : | ||
<nowiki>fibs :: [Integer] | <nowiki>fibs :: [Integer] | ||
− | fibs = | + | fibs = 1 : 1 : zipWith (+) fibs (tail fibs)</nowiki> |
− | ::::The first two numbers are | + | ::::The first two numbers are 1, 1 and you get the rest by adding fibs and tail fibs (fibs offset by 1 element) (zipping them together with +). |
::::The surprising part is that fibs is used in its own computation but that's no problem since each needed element can be computed by the time you need it (we "primed the pump" with the first two elements) and Haskell has lazy evaluation (sometimes named "call-by-need"). | ::::The surprising part is that fibs is used in its own computation but that's no problem since each needed element can be computed by the time you need it (we "primed the pump" with the first two elements) and Haskell has lazy evaluation (sometimes named "call-by-need"). | ||
::::Note that this version only compute each element once, contrary to the previous one (which is horrendous since it does the whole inefficient (O(fib n)) Fibonacci computation for each element). | ::::Note that this version only compute each element once, contrary to the previous one (which is horrendous since it does the whole inefficient (O(fib n)) Fibonacci computation for each element). |