All geek questions in one place

Give an endless list to skip every factor p?

How can I effectively represent the list [0..] \\ [t+0*p, t+1*p ..] ?

I defined:

 Prelude> let factors pt = [t+0*p, t+1*p ..]

I want to efficiently present an infinite list, which is the difference [0..] and factors pt , but using \\ from Data.List requires too much memory for even medium lists:

 Prelude Data.List> [0..10000] \\ (factors 5 0) <interactive>: out of memory

I know that I can represent the values ​​between t+0*p and t+1*p with:

 Prelude> let innerList p1 p2 t = [t+p1+1, t+p1+2 .. t+p2-1] Prelude> innerList 0 5 0 [1,2,3,4]

However, recalculating and concatenating the innerList to increase the intervals seems clumsy.

Can I effectively represent [0..] \\ (factors pt) without calculating rem or mod for each element?

+4
source share
5 answers

For an infinite list [0..] \\ [t,t+p..] ,

 yourlist tp = [0..t-1] ++ [i | m <- [0,p..], i <- [t+m+1..t+m+p-1]]

Of course, this approach does not scale at all if you want to remove some other factors, for example

 [0..] \\ [t,t+p..] \\ [s,s+q..] \\ ...

in this case you will have to delete them in the sequence with minus mentioned in Daniel Fisher's answer. There is no magic bullet.

But there is also a union , with which it will be higher

 [0..] \\ ( [t,t+p..] `union` [s,s+q..] `union` ... )

the advantage is that you organize unions in a tree and achieve algorithmic improvement.

+7
source

You cannot use (\\) for this, because

 (\\) :: (Eq a) => [a] -> [a] -> [a] (\\) = foldl (flip delete)

the list of items you want to delete is endless, and the left fold never ends when the list it adds is endless.

If you prefer to use something already written than to write it yourself, you can use minus from data-ordlist .

Efficiency must be adequate.

Otherwise,

 minus :: Ord a => [a] -> [a] -> [a] minus xxs@ (x:xs) yys@ (y:ys) | x < y = x : minus xs yys | x == y = minus xs ys | otherwise = minus xss ys minus xs _ = xs
+3
source

You can use compiling a list with a predicate using rem :

 >>> let t = 0 >>> let p = 5 >>> take 40 $ [ x | x <- [1..], x `rem` p /= t ] [1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49]
+1
source

If you need efficiency, why should your solution use list comprehension syntax?

Why not something like this?

  gen' nip | i == p = gen' (n + p) 1 p gen' nip = (n+i) : gen' n (i+1) p gen = gen' 0 1

and then do

  gen 5
+1
source

Since you have bottom-up lists, you can simply lazily combine them:

  nums = [1..] nogos = factors pt result = merge nums (dropWhile (<head nums) nogos) where merge (a:as) (b:bs) | a < b = a : merge as (b:bs) | a == b = merge as bs | otherwise = error "should not happen"

Writing this in a general way so that we have a function that builds the difference of two infinite lists, provided that they are in ascending order, remains as an exercise. As a result, the following should be possible:

  [1..] `infiniteDifference` primes `infiniteDifference` squares

To do this, make it the left associative operator.

+1
source

Source: https://habr.com/ru/post/1497860/

More articles:


All Articles