Haskell Efficient Program

Question

I have this code:

trimorficos :: [Integer]
trimorficos = filter (trim) [0..]

trim :: Integer -> Bool
trim x = (show x) `isSuffixOf` (show (x^3))
      where a = show x
            b = show (x^3)

densityTrimorficos :: Integer -> Double
densityTrimorficos n = fromInteger (n - (genericLength (filter (<=10) trimorficos))) / fromInteger n

Why the last function densityTrimorficos doesn't work?

I think you're going to need to give more context about what you're asking about. What doesn't work? — Carcigenicate
– Carcigenicate, Commented Feb 14, 2018 at 17:29
It works, but if I put densityTrimorficos 10 doesn't do anything. But if you compile, it doesn't recognize a error — mathandtic
– mathandtic, Commented Feb 14, 2018 at 17:39
@mathandtic: well there is no error in a slow function. But what Carcigenicate means is that you should explain what the function is supposed to do. What problem does it aim to solve? — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Feb 14, 2018 at 17:50
Shouldn't filter be replaced with takeWhile, since trimorficos only increases. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Feb 14, 2018 at 17:56

chi · Accepted Answer · 2018-02-14 18:58:18Z

1

trimorficos is an infinite list.

filter (<=10) trimorficos will never produce the end-of-list [] at the very end. To do so, it should verify that, from a certain point onward, trimorficos contains only numbers >10, but that would require infinite time. Basically, filter will returns something like a:b:c:nonTerminating instead of a:b:c:[] = [a,b,c].

Consequently, genericLength fails to terminate, since it tries to evaluate nonTerminating into either d:... or [] but that requires infinite time.

As pointed out above in the comments, you probably want takeWhile (<=10) trimorficos instead, which will produce [] as soon as the first >10 number is encountered. Note that this will not check the rest of the list, unlike filter.

answered Feb 14, 2018 at 18:58

chi

117k4 gold badges143 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Haskell Efficient Program

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related