Finding n'th generation in the sequence 1 / 1 1 / 2 1 / 1 2 1 1

user_6751737 0
Viewed 150

I'm trying to build a Haskell program that does as the title says. Basically every cell corresponds to the cell before it, the 2nd cell implies that there is just one '1' in the previous cell, and the 3rd cell implies that there is two '1' in the previous cell and so on.

I'm very new to haskell and to it's syntax so I'm getting loads of errors which aren't helpful so I'm using this forum to get some help with it.

This is my code:

findGen :: a -> a
findGen(x) = (getList (x))!!x

getList :: a -> [a]
getList (0) = []
getList (1) = [1]
getList (x) = getList(x-1) : ys where 
                            y = Ord getList(x-1) 
                            zs = group y
                            ds = countify(zs)
                            ys = concat(ds)

group :: Eq a => [a] -> [[a]]
group [] = []
group (x:xs) = (x:ys) : group zs where (ys,zs) = span ((==) x )xs


countify :: [a] -> [a]
countify(x:xs) = (y:xs) where y = count(x)

What I was trying to do is like this: FindGen is just a function that returns the n'th element in the sequence. getList is the function that builds the sequence, I was trying to create it using Ord to the previous list so I could group it and then use count to figure out how many times each number appear using countify, and then concating the list making it a string. Trying to figure out where am I wrong, probably in the syntax because I think the idea is good.

Thanks

haskell
3 Answers

I am going to provide a different thought about it. Consider your list as following,

  1. there is a seed "1",
  2. To grow the list, you only need to rely on the previous element.

Therefore, it's a fixpoint by looking back to 1 element, which can be implemented by specifying a base case, and the inductive case, then concatenate them.

It results in a two liner.

import Data.List (group, sort)

genList :: [String]
genList = "1" : map grow genList
  where grow s = (group $ reverse $ sort s) >>= (\n@(h:_) -> show (length n) ++ [h])

main :: IO ()
main = putStrLn $ show $ take 13 genList

Hopefully it's correct,

["1","11","21","1211","1231","131221","132231","232221","134211","14131231","14231241","24132231","14233221"]
user_30400640

I was trying to create it using Ord

If you want to sort a list, use sort (from Data.List if I remember correctly)

Also, note that the compiler will not accept getList because of the wrong type signature you supplied. Use Integer instead of a and it will be ok. Fix the signature for findGen the same way. Or better yet, until you get more familiar with the type system, don't give type signatures at all.

Furthermore, what is count? And why would you need to re-implement group?

user_866040

If i have the pattern right you may do this by using Data.Map and using iterate from Data.List in a lazy fashion as follows; (Thanks to @luqui's simplification on the map side)

import qualified Data.Map.Lazy as M

makeMap :: String -> M.Map Char Int
makeMap cs = foldr incrementOr1 M.empty cs
             where 
             incrementOr1 c m | M.member c m = M.alter (fmap (+1)) c m
                              | otherwise    = M.insert c 1 m
makeMap :: String -> M.Map Char Int
makeMap = M.fromListWith (+) . map (flip (,) 1)

generateList :: [String]
generateList = iterate getChrCnt "1"
               where
               getChrCnt = M.foldrWithKey (\k n a -> a ++ show n ++ [k]) "" . makeMap

*Main> take 13 $ generateList
["1","11","21","1211","1231","131221","132231","232221","134211","14131231","14231241","24132231","14233221"]

Interestingly it doesn't go anywhere beyond the 13th iteration which results "14233221". Just converged.

user_45432070
Related