Filter bigger element of two lists

Viewed 87

I am trying to write a Haskell programm which outputs a list of primes, but only those where the square is bigger than the product of the previous and following prime. For example, given

primes = [2, 3, 5, 7, 11, 13, 17]
-- keep  5 since  5² > 3*7
-- keep 11 since 11² > 7*13

My plan was to create the list of the squares and the neighbour products and then use a filter to output only those elements of the list of primes where the square is bigger than the neighbour products. This is what I have so far

products :: [Int]
products = zipWith (*) primes (drop 2 primes)

squares :: [Int]
squares = zipWith (*) (drop 1 primes) (drop 1 primes)

goodPrimes :: [Int]
goodPrimes = filter (\products, squares -> squares > products) (drop 1 primes)

Everything works but the goodPrimes function. I hope everything is clear and that someone can help me.

3 Answers

You had a syntax error in your goodPrimes lambda (a comma between params).

We also need to pair the elements of your products, squares, and primes lists (using zip3).

primes :: [Int]
primes = [2, 3, 5, 7, 11, 13, 17]

squares :: [Int]
squares = zipWith (*) (tail primes) (tail primes)

products :: [Int]
products = zipWith (*) primes (drop 2 primes)

goodPrimes :: [Int]
goodPrimes = fmap (\(prime, _, _) -> prime)
  $ filter (\(prime, prod, square) -> square > prod)
  $ zip3 (tail primes) products squares

We can inline the computation of the square to make goodPrimes cleaner, we can then delete squares.

goodPrimes :: [Int]
goodPrimes = fmap fst
  $ filter (\(prime, prod) -> prime * prime > prod)
  $ zip (tail primes) products
λ> goodPrimes
[5,11]

You were in the right direction, but not quite. To continue your line of thought we could write

goodPrimes = -- filter (\products, squares -> squares > products) (drop 1 primes)
  map (\ (_,_,p) -> p) $
    filter (\ (product, square, prime) -> square > product ) 
           (zip3 products 
                 squares
                 (drop 1 primes))

packaging the squares, the products, and the primes together into triples, filtering the triples, and then recovering the primes back. This is known as decorate-process-undecorate paradigm, or "Schwartzian transform" in the olden days of yore.

Or we could re-implement filter with a list comprehension, fusing all the definitions and simplifying the result to

goodPrimes2 = 
  [ prime | ((prod, sq), prime) <- products `zip` squares `zip` drop 1 primes
          , sq > prod ]
 =
  [ prime | ((prod, sq), prime) <- 
               zipWith (*) primes (drop 2 primes)
                 `zip` zipWith (*) (drop 1 primes) (drop 1 primes)
                   `zip` drop 1 primes
          , sq > prod ]
 =
  [ p1    | ((p0, p2), p1) <- 
               primes `zip` (drop 2 primes) `zip` drop 1 primes
          , p1*p1 > p0*p2]
 =
  [ p1    | (p0:p1:p2:_) <- iterate tail primes  -- or (tails primes)
          , p1*p1 > p0*p2]

(p0:p1:p2:_) is a list which, in pseudocode, could be written as [p0, p1, p2, ...], and iterate tail (or tails) produces a list of progressive tails of its input list, here primes.

There's no reuse of products and squares, so no point in pre-calculating those lists.

Trying it out:

> take 20 primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

> take 10 goodPrimes2
[5,11,17,29,37,41,53,59,67,71]

It can be nice to play with code, to shake it until it settles into something simple and clear. The sequence could be continued as

 =
  [ p1    | (p0:p1:p2:_) <- iterate tail primes  -- or (tails primes)
          , p1*p1 > p0*p2]
 =
  concatMap (\ case (p0:p1:p2:_) -> [p1 | p1*p1 > p0*p2] )
            (tails primes)
 =
  tails primes >>= (\ case (p0:p1:p2:_) -> [p1 | p1*p1 > p0*p2] )

Thus,

goodPrimes3 = foo primes
   where
   foo = tails >=> (\ case (p0:p1:p2:_) -> [p1 | p1*p1 > p0*p2] )

but these last variants which treat lists as a "monad" are probably not interesting for you right now.

Incidentally, the mapping on progressive tails is a primitive in Common Lisp, known as maplist, and the concat-mapping ("flatmapping" as it is known in other languages) on tails is also a primitive there, mapcon (so in Haskell, mapcon f = (tails >=> f)).

You can take this a step further by using zip3 to get tuples containing all three relevant values; then a simple list comprehension will give you the final result.

> zip3 <*> tail <*> tail.tail $ primes
[(2,3,5),(3,5,7),(5,7,11),(7,11,13),(11,13,17)]
> [ y | (x, y, z) <- zip3 <*> tail <*> tail.tail $ primes, y*y > x*z]
[5,11]

zip <*> tail $ primes is a nice idiom for generating a list of adjacent pairs. I'm not sure zip3 <*> tail <*> tail.tail $ primes is quite as nice. The explicit form is zip3 primes (tail primes) (tail (tail primes)).

Related