Take the 2-minute tour ×

I have a function:

isItSimple :: Int -> Bool

it gets Int and return Bool.

I need to find first number in [x | x <- [n..], isItSimple x].

Here is my solution:

findIt :: Int -> Int
findIt num
       | isItSimple num = num
       | otherwise = findIt (num + 1)

Is there any better solution in Haskell?

share|improve this question
yes, until isItSimple (1+). Expresses the same pattern, already captured in the Prelude. It is even named similarly. –  Will Ness May 8 at 5:19
add comment

5 Answers

up vote 6 down vote accepted

In most cases, especially when your problem is a particular case of solved one, explicit resursion is bad. One of possible solutions of your problem without using explicit recursion is:

import Data.List (find)
import Data.Maybe (fromJust)

findIt :: Int -> Int
findIt n = fromJust $ find isItSimple [n..]
share|improve this answer
Doesn't it depend on the complexity of the problem and the solution? If explicit recursion is simpler than knowing about find and fromJust, shouldn't one prefer using explicit recursion? –  Jaywalker Dec 3 '10 at 10:29
@Jaywalker: It is exactly the same, and more elegant. –  Alexandre C. Dec 3 '10 at 10:30
Can anyone elaborate on what "explicit recursion is bad" means. Bad performance? Uglyness? –  Martin Capodici Dec 10 '12 at 0:37
add comment


How about just like you said.

findIt n = head [ x | x <- [n..], isItSimple x ]
share|improve this answer
Definitly preferable over fromJust. –  FUZxxl Dec 3 '10 at 14:56
@FUZxxl I don't like fromJust in general but in this case, it's exactly the same as head, I mean having no x above n satisfying isItSimple will yield "bottom". We would never evaluate head [] nor fromJust Nothing anyway. –  gawi Dec 3 '10 at 19:47
hm... yes. You're right. –  FUZxxl Dec 4 '10 at 8:26
add comment

While the other answers work, they're arguably not the most idiomatic way to solve this problem in Haskell. You don't really need any extra imports: a couple of functions from the Prelude will do the trick.

I'd start by creating a list of all of the simple numbers greater than or equal to n. The function filter :: (a -> Bool) -> [a] -> [a] makes this easy:

filter isItSimple [n..]

Like [n..] this is an infinite list, but this isn't a problem since Haskell is lazy and won't evaluate anything until it's needed.

To get what you want you can just take the head of this infinite list:

findIt :: Int -> Int
findIt n = head $ filter isItSimple [n..]

Some people don't like head since it's a partial function and will raise an exception when it's given an empty list. I personally wouldn't worry about that here, since we know it will never be called on an empty list. It makes me much less uncomfortable than fromJust, which is also a partial function (it raises an exception when given Nothing) and in my opinion is always a bad idea.

(And speaking of personal taste, I'd write this as follows:

findIt = head . filter isItSimple . enumFrom

This is an example of pointfree style, which can get convoluted but in this case is very elegant, in my opinion.)

share|improve this answer
Worrying about head or fromJust is superfluous in this case anyhow, since if no simple numbers exist the program will go into an infinite loop first. But I agree that fromJust is almost never a good idea; at least use fromMaybe (error "What? Inconceivable!") to make it obvious what is going on. –  C. A. McCann Dec 3 '10 at 15:29
@camccann: Right, but for me the worrying is more a matter of developing better coding habits. I think I write nicer code if I force myself to pretend that fromJust doesn't exist. –  Travis Brown Dec 3 '10 at 15:42
add comment
findIt :: Int -> Int
findIt num = head $ dropWhile (not isItSimple) [num..]

I don't know if it's better. It just came to my mind.

share|improve this answer
should've been (not . isItSimple), with the dot (function composition). –  Will Ness May 8 at 7:52
add comment

Another way is to use the least fixed point combinator (fix in Data.Function)

findIt = fix (\f x ->  if isItSimple x then x else f (x + 1))

In this case it looks a little bit over-engineered, but if the "search space" follows a more complicated rule than x + 1 this technique can be quite useful.

share|improve this answer
Don't mistake fix for being anything other than recursion. By mechanical substitution: findIt x = if isItSimple x then x else findIt (x + 1). –  luqui Dec 5 '10 at 1:54
IOW, head . dropWhile (not . isItSimple) . iterate (1+), or even just until isItSimple (1+). –  Will Ness May 8 at 5:17
add comment

Your Answer


