Haskell: Functions that sometimes return a function

Question

Hoe do you write a function that can either return a value or another function?

For example:

Function Foo (x)
    If X = 0 Return "Done" 
    Else Return a Function that calls Foo(x-1)

Answer 1

You need to think about the types of your function: if Foo is of type (Int -> t), what is t? It needs to return something of type t in both cases. I think this is a little hard, because I don't think t can be String type or a function type (->) in the same function.

Answer 2

In haskell the return type of a function can only depend on the type of its arguments and, in case of functions with polymorphic return types, how the return value is used. In particular the return type of the function can not depend on the value of the argument.

In other words: you can't do what you want directly. In cases where you want to return one of two types, you can usually the type Either a b which is defined as data Either a b = Left a | Right b, which allows you to return a value of type a wrapped in a Left or a value of type b wrapped in a Right. You could then use pattern matching to retrieve the value in a type safe manner.

However since in this case the type for b would have to be infinite this does not work and you have to define your own wrapper type for this. Like so:

data MyResult = Str String | Fun ( () -> MyResult)
foo 0 = Str "done"
foo x = Fun (\ () -> foo (x-1))

foo now has type Num a => a -> MyResult. However every time you call foo you have to pattern match to see whether you got back a Str with a string inside or a Fun with a function inside.

Also note that if you want to return a function rather than a value in order to delay execution, this doesn't make sense in haskell because it is lazy and things generally don't get evaluated before they are used.

Answer 3

I know this doesn't answer your question directly, but I think you need to expand your idea about what it means to "return a function". For example the function:

mean3 :: Float -> Float -> Float -> Float
mean3 x y z = (x + y + z) / 3

Can be thought of as "taking 3 numbers and returning a number". Or it can be thought of as "a function taking two numbers, and returning a function from a number to a number":

mean3 :: Float -> Float -> (Float -> Float)

mean1 :: (Float -> Float)
mean1 = mean3 1 2

Answer 4

foo x =
    if x<=0 then "Done"
            else foo2 (x)

foo2 x = foo (x-1) ++ foo (x-1)

Found a non-trivial example. This seems to work.

Answer 5

Just following up from sepp2k's great answer. I think you're missing a fundamental concept in Haskell - you're always returning a function. Even a "value" of sorts is a function.

For example, bust open ghci and try:

> :t 5
:: (Num t) => t

Just a function that takes no input, return value is a Num.

> :t "What  is this?"
:: [Char]

Likewise, just a function that takes no value, returns [Char]

"But these are all just values! I'm not convinced!"

What's main then? (Supposing you've got it defined):

> :t main
:: IO ()

Just a function that returns an IO () instance.

Answer 6

{-# LANGUAGE ExistentialQuantification #-}

data MyResult = Str String | forall a. Fun a -- deriving Show

foo 0 = Str "done"
foo x = Fun (\ () -> foo (x-1))

that sort of works, but you can't derive an existential type (methinks) so you need to call foo like that: (\(Main.Str x) -> x) (Main.foo 0).

If you know how to get Main module into focus in ghci please post a comment.

Answer 7

From the looks of your pseudo code, I'm guessing you're expecting to return a "nullary" function, that is one that takes no arguments, and will call 'Foo(x-1)' when invoked.

If this is so, then as pointed out at the end of sepp2k's answer, there is such need in Haskell - that is what happens by default. Specifically:

foo x = if x == 0 then "Done"
                  else foo(x-1)

does exactly this: The value returned by calling, say, foo(7) is a thing that when the program needs it's value will evaluate foo(6). The recursive call won't be evaluated inside the evaluation of the if expression.