Fibonacci n-step number sequences: Difference between revisions
m
→{{header|Haskell}}: Added an example using unfoldr
m (→{{header|Haskell}}: Added an example using unfoldr) |
|||
Line 2,074:
nonanaccci -> [1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144]
decanaccci -> [1,1,2,4,8,16,32,64,128,256,512,1023,2045,4088,8172]</pre>
or in terms of '''unfoldr''':
{{Trans|Python}}
<lang haskell>import Data.Bifunctor (second)
import Data.List (transpose, uncons, unfoldr)
------------ FIBONACCI N-STEP NUMBER SEQUENCES -----------
a000032 :: [Int]
a000032 = unfoldr (recurrence 2) [2, 1]
nStepFibonacci :: Int -> [Int]
nStepFibonacci =
unfoldr <$> recurrence
<*> (($ 1 : fmap (2 ^) [0 ..]) . take)
recurrence :: Int -> [Int] -> Maybe (Int, [Int])
recurrence n =
( fmap
. second
. flip (<>)
. pure
. sum
. take n
)
<*> uncons
--------------------------- TEST -------------------------
main :: IO ()
main =
putStrLn $
"Recurrence relation sequences:\n\n"
<> spacedTable
justifyRight
( ("lucas:" : fmap show (take 15 a000032)) :
zipWith
(\k n -> k : fmap show (take 15 $ nStepFibonacci n))
(words "fibo tribo tetra penta hexa hepta octo nona deca")
[2 ..]
)
------------------------ FORMATTING ----------------------
spacedTable ::
(Int -> Char -> String -> String) -> [[String]] -> String
spacedTable aligned rows =
let columnWidths =
fmap
(maximum . fmap length)
(transpose rows)
in unlines $
fmap
(unwords . zipWith (`aligned` ' ') columnWidths)
rows
justifyRight :: Int -> Char -> String -> String
justifyRight n c = (drop . length) <*> (replicate n c <>)</lang>
{{Out}}
<pre>Recurrence relation sequences:
lucas: 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843
fibo 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
tribo 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136
tetra 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536
penta 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930
hexa 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617
hepta 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936
octo 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080
nona 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144
deca 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172</pre>
=={{header|Icon}} and {{header|Unicon}}==
| |||