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)
+1  A: 

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.

Of course it can - that's the point of the `Either` type suggestion many folks have suggested.
+17  A: 

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.

So there's no unified base type like we have in .NET or almost have in Java?
Jonathan Allen
@JonathanAllen: There's not only no common base type, there is no subtyping at all.
Though I should add that in many cases where you'd rely on subtyping in OO languages, haskell's parametric polymorphism allows you to achieve the same effect in a different way.
More importantly, there's no general means of inspecting a value to determine its type. Which is a *good* thing, because it means we can be confident that polymorphic functions will behave consistently for all arguments.
@camccann: I'd consider that a consequence of the lack of subtyping. It makes no sense to inspect a value's type at runtime if the type is already fully known at compile time.
I'm not sure what you mean--having subtyping relationships doesn't prevent types being known at compile-time, and run-time type inspection would work just as well without any subtyping as such. The two seem completely orthogonal to me...
@camccann: `foo instanceof Bar` in java makes sense if and only if the static type of foo is a supertype of Bar. Otherwise it would always be false. In haskell `foo instanceof Bar` would always return true (in case where the static type of foo is Bar) or always return false (in case it's not). Neither of which would be useful. The point is in java you don't know whether a variable of type Object really contains a String or an ArrayList (as an example). In haskell you always know the type, so you don't need to check it.
I think it is disingenuous to say you don’t inspect a value's type at run time. Pattern matching on an Either is for all intents and purposes runtime type inspection. There is no practical difference between it and a Variant type would be in C.
Jonathan Allen
@JonathanAllen: If I do `case x of Left a ...` I'm not expecting the type of x. The type of x is `Either foo bar`, I know that, there's no need to inspect that. I'm inspecting the contents of x. The same is true for variant types in a way, but the variant may contain a void pointer, which you would not statically know the type of. Either way when I talked about "runtime type inspection" I was talking about reflection in the Java/C# sense, not about "handmade" workarounds, which exist only because C you *can't* inspect a value's type at runtime...
... Yes, Either is a way to work around the fact, that you can't return multiple types, but it's still fully statically typed. It's different from variant types in that you can't possibly define an Either-equivalent that behaves badly or get a `foo` out of an Either that contains a `Bar` without the compiler noticing.
I get the following when running your code. Same occurs for () as the argument. What am I doing wrong?' Occurs check: cannot construct the infinite type: b = a -> Either [Char] b Expected type: Either [Char] b Inferred type: Either [Char] (a -> Either [Char] b) In the expression: Right (\ x -> foo (x - 1)) In the definition of `foo': foo x = Right (\ x -> foo (x - 1))Failed, modules loaded: none.'
@DonnyD: Brilliant. I just got 11 upvotes for an answer that is wrong and you're the first to notice ;-) Fix coming up.
@sepp2k Sorry I voted you up, but this dang iPhone doesn't run ghc. ;-)
Owen S.
Irrespective of any specific examples, I am grateful for this thread. I've learned more in a day than I have in the past week just by reading the back and forth. Thanks sepp2k.
+1  A: 

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
That seems rather limiting. What if I don't know how many numbers it should take ahead of time?
Jonathan Allen
@Jonathan Allen: make a function taking a list.
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.

You're still applying the function, not returning one. (Also note that this causes an infinite loop if you call foo with an odd argument or foo2 with an even argument (or either with a negative one, but that's not new)).
I see now about function application vs. function return. It pays to read the question. The code has at least now been edited and should be better behaved.
+1  A: 

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.

I don't agree with this. A function is something that can be applied. You can't apply a string. Anything that does not match the type `a -> b` (for some a and b) is not a function.
So this isn't a function? void foo (){ printf("Hello");}
In Haskell, it would either have the type `() -> IO ()`, in which case it would be a function; or it would have the type `IO ()`, in which case it would be a value which is, roughly speaking, an "IO action". In C, too, you *do* have to apply it, by writing `foo()`.
Antal S-Z
@sepp2k: I'm 99% sure it's just semantics. I can't see any inconsistencies arising from defining a string as a function taking 0 arguments, which, when applied to 0 arguments, evaluates to itself -- and if so then it's a valid definition. (Just as your definition, in which a function can only be applied to 1 argument, is also valid since it doesn't lead to inconsistencies either.)
@Dan: I meant in Haskell. In impure languages we wouldn't even have to discuss the difference between simple values and function, because `string foo() { return "bla"; }` is clearly different from `string foo = "bla";`.
@j_random_hacker: Sure it's a matter of definition. The definition of Haskell (i.e. the Haskell 98 report) says the following: "A function type has the form t1 -> t2". If you use a definition that differs from that, you're going to run into trouble communicating with people who use the official definition. For example the statement that the argument to map can be any function is false if you define a string to be a function, too, while any haskeller would tell you it's true (unless you first tell him that you're operating under a different definition of the word "function").
@sepp2k: Ah, so Haskell does explicitly define the term "function" -- don't know why I'm surprised by that! In that case I totally agree it would be (at the very least) unproductive to use a non-canonical definition. "Withdrawn!" :)
@Antal: No, it would have the type _IO ()_I agree with sepp2k that saying that "blah" is a function is not really correct - at the very least, it's not going to make things clearer to the OP.
@Bill: Yes, I agree with sepp2k as well. But because C works the way it does, there are two possible translations of the C function `foo` into Haskell; and indeeed, one of these two ways gives rise to a function. Admittedly, the translation as a function is odd and not something I'd expect to see, but it is possible, and makes sense in an eager language like C.
Antal S-Z
@Antal: No. There's no reason to have a function of type () -> IO (). The type is IO (). You can add an arbitrary number of ignored unit parameters (e.g. () -> () -> () -> IO ()) but that would be strange and totally unnecessary.
@Bill: Yes, *in Haskell*. The, so to speak, Haskellized type of said function in C is `() -> IO ()`, or even `() -> ()`, because C is eager and effectful. Which is all I was saying: you can consider `void foo() { printf("Hello"); }` a function in C. And if you translate it to Haskell, you get one of two things: the odd *function* type `() -> IO ()`, even though with Haskell semantics that's useless; or the more sensible `IO ()` "IO action" (non-function) type.
Antal S-Z
Actually, if I recall correctly, you are effectively returning a function, because of lazy evaluation. However, this is hidden by Haskell mechanism and as such does not appear as a function in the Haskell language. Not sure I am clear.
Matthieu M.
{-# 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) ( 0).

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

+2  A: 

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.