时间戳

首页 > 解决方案 > 我怎样才能在 Haskell 中通过素数索引列出一个列表？

haskell - 我怎样才能在 Haskell 中通过素数索引列出一个列表？

问题描述

我怎样才能制作一个列表，让我得到每个具有素数索引号的数字/字母？

primeIndex :: [a] -> [a]
primeIndex [1..20] == [2, 3, 5, 7, 11, 13, 17, 19]
primeIndex "primesarefun" == "rieau"

标签： haskell

解决方案

一个可能的策略：

按照@Joseph Sible-Reinstate Monica 上面提到的一般方法，问题可以这样解决：

  1. 得到所有素数的列表，比如说primes
  2. 使用第一个列表创建一个布尔值的辅助列表，它的True元素仅在素数索引处
  3. 将第二个列表与经典列表函数（map、filter、zip）一起使用来解决问题

关于第一部分， Haskell Wiki的相关页面中有许多可用的算法。我们只能选择其中之一。

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

LME 代表线性合并。

关于第二部分，可以从SO_q59092535primes中获取转换为所需布尔值列表的函数，例如。primeMask

-- 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

把它们放在一起（第三部分和最后一部分）：

在一个ghci会话中：

 λ> 
 λ> 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]
 λ>

推荐阅读