How to resolve the algorithm Recaman's sequence step by step in the Haskell programming language

Published on 7 June 2024 03:52 AM
#Haskell

How to resolve the algorithm Recaman's sequence step by step in the Haskell programming language

Table of Contents

Problem Statement

The Recamán's sequence generates Natural numbers. Starting from a(0)=0, the n'th term a(n), where n>0, is the previous term minus n i.e a(n) = a(n-1) - n but only if this is both positive and has not been previousely generated. If the conditions don't hold then a(n) = a(n-1) + n.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Recaman's sequence step by step in the Haskell programming language

Haskell is a purely functional programming language and the code snippet you provided is an implementation of the Recaman's sequence using different approaches:

  • recaman n: computes the first n Recaman's numbers. Recaman's sequence is an infinite sequence of integers starting with 0 and is defined by the following rules:
  • The first term of the sequence is 0.
  • Each subsequent term is obtained by subtracting the previous term from the smallest non-negative integer that has not yet appeared in the sequence.
  • If the result of the subtraction is non-negative, then the result is the next term of the sequence.
  • Otherwise, the result plus the previous term is the next term of the sequence.
  • firstNRecamans n: computes the first n Recaman's numbers.
  • firstDuplicateR: computes the first duplicated Recaman's number.
  • recamanSuperset setInts: computes the length of the Recaman's series required to include the set of integers setInts.
  • recamanUpto p: computes the Recaman's series up to a predicate p.
  • nextR seen i r: computes the next Recaman's number based on the previous Recaman's number, the index, and the set of seen numbers.
  • rSeries: computes an infinite stream of Recaman's series of growing length.
  • rSets: computes an infinite stream of Recaman-generated integer sets of growing size.

The main function in the code snippet:

  • prints the first 15 Recaman's numbers
  • the first duplicated Recaman's number
  • the length of the Recaman's series required to include the set of integers [0..1000]

Source code in the haskell programming language

recaman :: Int -> [Int]
recaman n = fst <$> reverse (go n)
  where
    go 0 = []
    go 1 = [(0, 1)]
    go x =
        let xs@((r, i):_) = go (pred x)
            back = r - i
        in ( if 0 < back && not (any ((back ==) . fst) xs)
               then back
               else r + i
           , succ i) :
           xs

main :: IO ()
main = print $ recaman 15


import Data.Set (Set, fromList, insert, isSubsetOf, member, size)
import Data.Bool (bool)

firstNRecamans :: Int -> [Int]
firstNRecamans n = reverse $ recamanUpto (\(_, i, _) -> n == i)

firstDuplicateR :: Int
firstDuplicateR = head $ recamanUpto (\(rs, _, set) -> size set /= length rs)

recamanSuperset :: Set Int -> [Int]
recamanSuperset setInts =
  tail $ recamanUpto (\(_, _, setR) -> isSubsetOf setInts setR)

recamanUpto :: (([Int], Int, Set Int) -> Bool) -> [Int]
recamanUpto p = rs
  where
    (rs, _, _) =
      until
        p
        (\(rs@(r:_), i, seen) ->
            let n = nextR seen i r
            in (n : rs, succ i, insert n seen))
        ([0], 1, fromList [0])

nextR :: Set Int -> Int -> Int -> Int
nextR seen i r =
  let back = r - i
  in bool back (r + i) (0 > back || member back seen)

-- TEST ---------------------------------------------------------------
main :: IO ()
main =
  (putStrLn . unlines)
    [ "First 15 Recamans:"
    , show $ firstNRecamans 15
    , []
    , "First duplicated Recaman:"
    , show firstDuplicateR
    , []
    , "Length of Recaman series required to include [0..1000]:"
    , (show . length . recamanSuperset) $ fromList [0 .. 1000]
    ]


import Data.List (find, findIndex, nub)
import Data.Maybe (fromJust)
import Data.Set (Set, fromList, insert, isSubsetOf, member)

--- INFINITE STREAM OF RECAMAN SERIES OF GROWING LENGTH --
rSeries :: [[Int]]
rSeries =
  scanl
    ( \rs@(r : _) i ->
        let back = r - i
            nxt
              | 0 > back || elem back rs = r + i
              | otherwise = back
         in nxt : rs
    )
    [0]
    [1 ..]

----------- INFINITE STREAM OF RECAMAN-GENERATED ---------
--------------- INTEGER SETS OF GROWING SIZE -------------
rSets :: [(Set Int, Int)]
rSets =
  scanl
    ( \(seen, r) i ->
        let back = r - i
            nxt
              | 0 > back || member back seen = r + i
              | otherwise = back
         in (insert nxt seen, nxt)
    )
    (fromList [0], 0)
    [1 ..]

--------------------------- TEST -------------------------
main :: IO ()
main = do
  let setK = fromList [0 .. 1000]
  (putStrLn . unlines)
    [ "First 15 Recamans:",
      show . reverse . fromJust $ find ((15 ==) . length) rSeries,
      [],
      "First duplicated Recaman:",
      show . head . fromJust $ find ((/=) <$> length <*> (length . nub)) rSeries,
      [],
      "Length of Recaman series required to include [0..1000]:",
      show . fromJust $ findIndex (\(setR, _) -> isSubsetOf setK setR) rSets
    ]

You may also check:How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the zkl programming language
You may also check:How to resolve the algorithm Modular inverse step by step in the OCaml programming language
You may also check:How to resolve the algorithm Doubly-linked list/Element insertion step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Tree datastructures step by step in the Wren programming language
You may also check:How to resolve the algorithm Permutations/Rank of a permutation step by step in the zkl programming language