Call out: the Haskell one

[tel]

The Haskell one is super clever for a number of reasons!

1. Foremost, g() is not syntax for calling g with no arguments, it's syntax for calling g with a single argument: the empty tuple

2. There is no such thing as a polyvariadic (i.e. a function with "splat" arguments) function in Haskell! The type must indicate the exact set of arguments

3. Haskell is statically typed, so if you try to write a function which returns a function then the type would fix how many times you could apply an empty tuple. In other words, here's a simple function which returns g()()("al") --> "gooal"

   g :: () -> (() -> (String -> String))
   g = \() -> \() -> \string -> "goo" ++ string
   

   if it's not clear, there's no room for this function to suddenly accept a new tuple argument.

So, this seems pretty terrible. How does the solution work?

"Simple." We teach the compiler how to generate, on the fly, every possible function:

    g0(s) -- "g" ++ s
    g1()(s) -- "go" ++ s
    g2()()(s) -- "goo" ++ s
    g3()()()(s) -- "gooo" ++ s
    ...

then we name them all g. At compile time Haskell wanders around looking for (ambiguous) references to g, infers their type, and then uses that inferred type to determine which of the gN-series of functions is correct!

Then it inlines that gN function, typechecks it to prove that everything is sane, and goes on its merry way.

---

I said that Haskell demands we give exact types to all functions. So what's the type of g?

g :: (Goaly a, Stringy b) => b -> a

Here, Goaly and Stringy are defined in eatnumber1's solution. Roughly, they indicate polymorphism: b can be either () or a string indicating the two kinds of input types we're interested in and a is either a String (if we're demanding the result) or a "continuation" function of type (Goaly a, Stringy b) => b -> a again.

Together these cases ensure that we've got an inductive definition of the entire family of gN functions. We've actually defined something even larger, to be honest:

>>> g()"ooooo"()"al" :: String
"goooooooal"

We can even add more cases

instance Stringy Int where
  toString 0 = "o"
  toString n = show n
  (+++) x y = x ++ toString y

>>> default (Int)
>>> g()0()0()0()0()0()0"al" :: String
"gooooooooooooal"

[tel]

Finally, did I say this was all clever?

It is, definitely. But it also doesn't subvert the language spec at all. This is almost exactly a natural consequence of totally intended behavior of Haskell.

[eatnumber1]

Agreed, this is a great solution!

Giving credit where credit is due though, it's @capicue's doing. Not mine :)

[eatnumber1]

Great explanation too. I've added a link to this bug to the editor's picks

[Rufflewind]

Actually this can be done entirely with one type class:

{-# LANGUAGE FlexibleInstances #-}

class Goaly a where
    g' :: String -> a
    g  :: a
    g  = g' ""

instance Goaly (String -> String) where
    g' oo al = "g" ++ oo ++ al

instance Goaly a => Goaly (() -> a) where
    g' oo () = g' $ 'o' : oo

main = do
  putStrLn $ g("al")
  putStrLn $ g()("al")
  putStrLn $ g()()("al")
  putStrLn $ g()()()("al")