Verbose List Comprehension in Haskell

Question

I'm using Haskell to find a list of integers from 1 to 10000 that have a special property. I do the following

[ number | number <- [1..10000], (isSpecial number)]

However, every now and then I came up with some special properties that are

1. hard to be satisfied

2. take a long time to be verified

As a result, it hangs there after some first few examples.

I wonder how I can make the list comprehension in Haskell verbose, so I have a good update about how much Haskell has progressed.

Answer 1

This is more or less what Robin Zigmond meant:

checkNumbers :: IO [Int]
checkNumbers = filterM check [1..10000]
    where
        check number = do
            print $ "Checking number" <> show number
            pure $ isSpecial number

This will print "Checking number x" before checking every number. Feel free to experiment with any other effects (or, in your words, "verbosity") within the check function.

Answer 2

Here is a way that requires no IO, instead relying on laziness and your programmer guess about which "side" of the condition happens more often. Just to have something to play with, here's a slightly slow function that checks if a number is a multiple of 10. The details of this function aren't important, feel free to skip it if anything doesn't make sense. I'm also going to turn on timing reporting; you'll see why later.

> isSpecial :: Int -> Bool; isSpecial n = last [1..10000000] `seq` (n `mod` 10 == 0)
> :set +s

(Add one 0 every five years.)

Now the idea will be this: instead of your list comprehension, we'll use partition to split the list into two chunks, the elements that match the predicate and the ones that don't. We'll print the one of those that has more elements, so we can keep an eye on progress; by the time it's fully printed, the other one will be fully evaluated and we can inspect it however we like.

> :m + Data.List
> (matches, nonMatches) = partition isSpecial [1..20]
(0.00 secs, 0 bytes)
> nonMatches
[1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19]
(12.40 secs, 14,400,099,848 bytes)

Obviously I can't portray this over StackOverflow, but when I did the above thing, the numbers in the nonMatches list slowly appeared on my terminal one-by-one, giving a pretty good indicator of where in the list it was currently thinking. And now, when you print matches, the full list is available more or less instantly, as you can see by the timing report (i.e. not another 12-second wait):

> matches
[10,20]
(0.01 secs, 64,112 bytes)

But beware!

1. It's important that matches and nonMatches have types which are not typeclass polymorphic (i.e. don't have types that start with Num a => ... or some other constraint). In the above example, I achieved this by making isSpecial monomorphic, which forces matches and nonMatches to be, too, but if your isSpecial is polymorphic, you should give a type signature for matches or nonMatches to prevent this problem.

2. Doing it this way will cause the entire nonMatches and matches lists to be realized in memory. This could be expensive if the original list being partitioned is very long. (But up to, say, a couple hundred thousand Ints is not particularly long for modern computers.)

Answer 3

Debug.Trace

You can have a look at Debug.Trace. It allows printing messages to the console. But as Haskell is lazy, controlling when printing happens is not so easy. And this is also not recommended for production:

Prelude Debug.Trace> import Debug.Trace
Prelude Debug.Trace> [x | x <- [1..10], traceShow (x, odd x) $ odd x]
(1,True)
[1(2,False)
(3,True)
,3(4,False)
(5,True)
,5(6,False)
(7,True)
,7(8,False)
(9,True)
,9(10,False)
]

Answer 4

We would usually want to see both the tried and the discovered numbers as the calculation goes on.

What I usually do is break up the input list into chunks of n elements, filter each chunk as you would the whole list, and convert each chunk into a pair of its head element and the filtered chunk:

chunked_result = [ (h, [n | n <- chunk, isSpecial n])
                   | chunk@(h:_) <- chunksOf n input]

Putting such result list through concatMap snd gives the original non-"verbose" option.

Adjusting the n value will influence the frequency with which the progress will be "reported" when the result list is simply printed, showing both the tried and the discovered numbers, with some inconsequential "noise" around them.

Using second concat . unzip on the chunks results list is somewhat similar to Daniel Wagner's partitioning idea (with caveats),^(*) but with your set value of n, not just 1.

If there is an algorithmic slowdown innate to your specific problem, apply the orders of growth run time estimation analysis.

---

^(*) to make it compatible we need to stick some seq in the middle somewhere, like

chunked_result = [ (last s `seq` last chunk, s)
                   | chunk <- chunksOf n input
                     let s = [n | n <- chunk, isSpecial n] ]

or something.