repl.it
@pyelias/

the big confuse

Haskell

http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/

fork
loading
Files
  • main.hs
main.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
data InfSeq a = Cons a (InfSeq a)

class Findable a where 
  find :: (a -> Bool) -> a
  forany :: (a -> Bool) -> Bool
  forall :: (a -> Bool) -> Bool
  forany p = p (find p)
  forall p = not (p (find (not . p)))

instance Findable Bool where
  find p = if p False then False else True

instance (Findable a) => Findable [a] where
  find p = if (p [])
           then []
           else first : find (prepend first p)
                where first = find canBeFirst
                      canBeFirst a = forany (prepend a p)
                      prepend a p = p . (a:)

instance (Findable a) => Findable (InfSeq a) where
  find p = Cons first (find (prepend first p))
           where first = find canBeFirst
                 canBeFirst a = forany (prepend a p)
                 prepend a p = p . Cons a

countOnes :: InfSeq Bool -> Integer
countOnes (Cons True rest) = 1 + countOnes rest
countOnes _ = 0

toList _ 0 = []
toList (Cons first rest) n = first : toList rest (n - 1)

main = print (toList (find (\b -> (countOnes b) > 5)) 10)
GHCi, version 8.6.5
?