module Task05 where import Prelude hiding (($)) import Test.QuickCheck -- Note that this…
- User
module Task05 where import Prelude hiding (($)) import Test.QuickCheck
-- Note that this is the first non-CodeWorld-task.
-- Consider the following function computing -- Tribonacci numbers:
trib :: Integer -> Integer trib 0 = 0 trib 1 = 1 trib 2 = 1 trib n = trib (n - 3) + trib (n - 2) + trib (n - 1)
{- Here is a more efficient version written in Python, using mutable variables:
def tribonacci(n): if n <= 0: return 0 elif n <= 2: return 1 else: a, b, c = 0, 1, 1 count = n - 2 while count > 0: a, b, c = b, c, a + b + c count -= 1 return c
-}
-- Write a Haskell function that follows the same idea, avoiding -- the inefficiency of having three recursive calls for each -- nontrivial case.
-- By executing 'main' below, you can partially test your solution -- before uploading it.
tribonacci :: Integer -> Integer tribonacci = undefined
main :: IO () main = do putStrLn "Some simple test cases:" quickCheck (tribonacci 5 == 7) quickCheck (tribonacci 6 == 13) quickCheck (tribonacci 10 == trib 10) putStrLn "Checking further cases, while being careful to not go too high:" quickCheck ((NonNegative n) -> (n < 25) ==> (tribonacci n == trib n))
- Assistant
To rewrite the provided Python code in Haskell, while avoiding the inefficiency of multiple recursive calls in the
tribfunction, we can define a helper function in Haskell that iterates a fixed number of times, similarly to the while loop in Python. This helper will recursively update its state(a, b, c)until it reaches the desired iteration. Here's how:module Task05 where import Prelude hiding (($)) import Test.QuickCheck tribonacci :: Integer -> Integer tribonacci n | n <= 0 = 0 | n <= 2 = 1 | otherwise = helper 0 1 1 (n - 2) -- We start with a=0, b=1, c=1 and need to perform n-2 iterations where helper a b c count | count == 0 = c -- Return c when count reaches 0 | otherwise = helper b c (a + b + c) (count - 1) -- Perform the next iteration main :: IO () main = do putStrLn "Some simple test cases:" quickCheck (tribonacci 5 == 7) quickCheck (tribonacci 6 == 13) quickCheck (tribonacci 10 == trib 10) putStrLn "Checking further cases, while being careful to not go too high:" quickCheck (\(NonNegative n) -> (n < 25) ==> (tribonacci n == trib n))This function
tribonaccifollows the same logic as your Python code. It uses a helper functionhelperwith parametersa,b,c, andcountto track its state as it iteratesn-2times (as in the Python code after initializinga,b,c, we loopn-2times). Each iteration updates the values ofa,b, andcto their new values, which respect the Tribonacci sequence rule. Whencountreaches 0, the function returns the current value ofc, which is the desired Tribonacci number at positionn. The base cases forn <= 0andn <= 2are handled explicitly at the beginning of the function.