0

How could I make a list where I get every number/letter which has a prime index number?

primeIndex :: [a] -> [a]
primeIndex [1..20] == [2, 3, 5, 7, 11, 13, 17, 19]
primeIndex "primesarefun" == "rieau"
peter.s
  • 67
  • 3
  • Take a look at the [*sieve of Eratosthenes*](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) – Willem Van Onsem Dec 14 '19 at 17:14
  • This is really two questions in one. The first is how you find prime numbers in Haskell, and the second is how you filter a list by the elements' indices (as opposed to the usual case of filtering by their values). @WillemVanOnsem provided a link that will help with the first. Which of the pieces are you stuck on? – Joseph Sible-Reinstate Monica Dec 14 '19 at 17:36
  • Why do you need the items at the prime indices..? – Redu Dec 14 '19 at 17:58

1 Answers1

0

A possible strategy:

Following the general approach mentioned above by @Joseph Sible-Reinstate Monica, the problem can be solved like this:

  1. get a list of all prime numbers, say primes
  2. use that first list to create an auxiliary list of booleans which has True elements solely at prime indices
  3. use the second list together with classic list functions (map, filter, zip) to solve the problem

Regarding the first part, there are a number of available algorithms in the relevant page of the Haskell Wiki. We can just pick one of them.

import  Data.List.Ordered

_Y   :: (t -> t) -> t
_Y g = g (_Y g)    

joinL :: (Ord a, Eq a) => [[a]] -> [a]
joinL ((x:xs):t) = x : union xs (joinL t)
joinL ([]:t)     = joinL t
joinL  []        = []

primesLME :: [Integer]
primesLME = 2 : _Y ((3:) . minus [5,7..] . joinL . map (\p-> [p*p, p*p+2*p..]))

primes = primesLME

with LME standing for Linear MErging.

Regarding the second part, a function to transform primes into the required list of booleans, say primeMask, can be taken from SO_q59092535.

-- boolean list from index list (with unfoldr):
booleansFromIndices :: [Integer] -> [Bool]
booleansFromIndices indices =
    let  sfn (pos,ind) =  Just $  -- stepping function for unfoldr
             if (null ind)
               then ( False, (pos+1, []) )
               else ( pos==head ind,
                      (pos+1, if (pos==head ind)  then  tail ind  else  ind))
    in   unfoldr  sfn  (0,indices)

primeMask :: [Bool]
primeMask = drop 1 $ booleansFromIndices primes  -- 1-based indexing

Putting it all together (third and last part):

In a ghci session:

 λ> 
 λ> take 10 primes
[2,3,5,7,11,13,17,19,23,29]
 λ> 
 λ> 
 λ> take 15 primeMask
[False,True,True,False,True,False,True,False,False,False,True,False,True,False,False]
 λ> 
 λ> take 20 $ map  (\b -> if b then '1' else '0')  primeMask
"01101010001010001010"
 λ> 
 λ> str = "primesarefun"
 λ> 
 λ> zip primeMask str
[(False,'p'),(True,'r'),(True,'i'),(False,'m'),(True,'e'),(False,'s'),(True,'a'),(False,'r'),(False,'e'),(False,'f'),(True,'u'),(False,'n')]
 λ> 
 λ> filter fst $ zip primeMask str
[(True,'r'),(True,'i'),(True,'e'),(True,'a'),(True,'u')]
 λ> 
 λ> map snd $ filter fst $ zip primeMask str
"rieau"
 λ> 
 λ> primeIndex = \xs -> map snd $ filter fst $ zip primeMask xs
 λ> 
 λ> primeIndex [1..20]
[2,3,5,7,11,13,17,19]
 λ>
jpmarinier
  • 4,427
  • 1
  • 10
  • 23