Hi, Am Donnerstag, den 14.10.2010, 09:34 +0200 schrieb Jacek Generowicz:

Another example:

Let's say I need an Int -> String. Both

(fnA2 :: Banana -> String) . (fnA1:: Int -> Banana)

and

(fnB2 :: Onion -> String) . (fnB1 :: Int -> Onion)

will do. So please allow me to store (fnA1, fnA2) and (fnB1, fnB2) in the same place. The program can tell that it can combine them with (.) because the type of

let (fn1, fn2) = pair in fn2 . fn1

is always

Int -> String.

This is possible: {-# LANGUAGE ExistentialQuantification #-} data SplitFun a b = forall x. SplitFun (a -> x, x -> b) splitFuns :: [SplitFun Int String] splitFuns = [SplitFun (\n -> replicate n "hi", concat) ,SplitFun (show, id)] main = mapM_ putStrLn $ map (\(SplitFun (f1,f2)) -> f2 (f1 2)) splitFuns This prints: *Main> main hihi 2 Greetings, Joachim -- Joachim "nomeata" Breitner mail: mail@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nomeata@debian.org

On 14 October 2010 08:34, Jacek Generowicz wrote:

Those other data might be the functions' arguments, or they might be other functions with which they are to be combined, or both.

You can represent these as existential packages. However, as Oleg shows you can always use skolemisation to eliminate the existential: http://okmij.org/ftp/Computation/Existentials.html This trick is basically what Brandon and Evan pointed out earlier when they suggested you replace the list :: [exists b. (b -> a, b)] with a list :: [a].

Here's an example where lazy evaluation isn't enough:

def memoize(fn):    cache = {}    def memoized_fn(*args):        if args not in cache:            cache[args] = fn(*args)        return cache[args]    return memoized_fn

You memoize a function once, but it will be given different arguments, many times, at a later time.

I'm not sure why you would use existentials for this. Isn't the type of memoized_fn just :: Ord a => (a -> b) -> a -> b? This doesn't deal with argument *lists* so you may have to curry/uncurry to get functions of a different arity to go through, but that is IMHO a reasonable requirement for Haskell, where multi-argument functions do not have special status. (In the absence of side effects, I can't see an obvious way to implement it without some way to enumerate the domain "a" though. Conal Elliot uses type classes to solve this issue, see http://hackage.haskell.org/package/MemoTrie, where memo :: HasTrie t => (t -> a) -> t -> a).

will do. So please allow me to store (fnA1, fnA2) and (fnB1, fnB2) in the same place. The program can tell that it can combine them with (.) because the type of

But if the only operation you ever do on this pair is (.), you may as well skolemise and just store (fnA1 . fnA2) directly. What is the advantage of doing otherwise? Max

On 2010 Oct 14, at 09:56, Max Bolingbroke wrote:

On 14 October 2010 08:34, Jacek Generowicz wrote:

...

Those other data might be the functions' arguments, or they might be other functions with which they are to be combined, or both.

You can represent these as existential packages. However, as Oleg shows you can always use skolemisation to eliminate the existential: http://okmij.org/ftp/Computation/Existentials.html

This trick is basically what Brandon and Evan pointed out earlier when they suggested you replace the list :: [exists b. (b -> a, b)] with a list :: [a].

Aaah. The link between the last two paragraphs is important. Thanks very much.

...

Here's an example where lazy evaluation isn't enough:

def memoize(fn): cache = {} def memoized_fn(*args): if args not in cache: cache[args] = fn(*args) return cache[args] return memoized_fn

You memoize a function once, but it will be given different arguments, many times, at a later time.

I'm not sure why you would use existentials for this. Isn't the type of memoized_fn just :: Ord a => (a -> b) -> a -> b?

I don't think so. The Python Duck Type of memoized_fn (and fn), expressed in Haskell syntax is a -> b | a -> b -> c | a -> b -> c -> d | etc. The type of memoize would be (a -> b) -> a -> b | (a -> b -> c) -> a -> b -> c | (a -> b -> c -> d) -> a -> b -> c -> d | etc. Which is the whole point of the * in *args. (Not sure why you specified Ord a. In Python you *would* need Hashable a,b,c,d.) Of course, you could argue that the type is (a -> b) -> a -> b | (a -> b -> c) -> (a, b) -> c | (a -> b -> c -> d) -> (a, b, c) -> d | etc. But does that change things significantly?

This doesn't deal with argument *lists* so you may have to curry/uncurry to get functions of a different arity to go through, but that is IMHO a reasonable requirement for Haskell, where multi-argument functions do not have special status.

I would argue that easily dealing with different arities is an important requirement of the "arithmetic test" motivating example.

(In the absence of side effects, I can't see an obvious way to implement it without some way to enumerate the domain "a" though. Conal Elliot uses type classes to solve this issue, see http://hackage.haskell.org/package/MemoTrie, where memo :: HasTrie t => (t -> a) -> t -> a).

Thanks for the heads-up.

...

will do. So please allow me to store (fnA1, fnA2) and (fnB1, fnB2) in the same place. The program can tell that it can combine them with (.) because the type of

But if the only operation you ever do on this pair is (.), you may as well skolemise and just store (fnA1 . fnA2) directly. What is the advantage of doing otherwise?

(.) is not the *only* operation I will do. But I think that's a red herring. Regardless of what operation I will do, I think that the problem is that some of the components are known earlier than others. But I think that currying trivially solves this particular problem. So I think that, as you say, skolemisation will do the trick. Though I still haven't delved sufficiently into the article you cite at the top, to be sure that extensibility won't be curtailed by this approach. If it is, then existentials should do the job.

On 2010 Oct 14, at 09:58, Ketil Malde wrote:

Jacek Generowicz writes:

...

Let's say I need an Int -> String. Both

(fnA2 :: Banana -> String) . (fnA1:: Int -> Banana)

and

(fnB2 :: Onion -> String) . (fnB1 :: Int -> Onion)

will do. So please allow me to store (fnA1, fnA2) and (fnB1, fnB2) in the same place.

I think you can do this fairly easy with existentials, but..

Yup, that's got through to me by now :-)

...

The program can tell that it can combine them with (.)

..what else do you want to be able to do with them? (Because, if this is all, you'd just store the combination, no?).

Yes, if the components became available at the same time. But they don't. However, I think that currying caters for this separate arrival time problem. Hmm, except that I would like to be able to store a collection of incomplete combinations and say "complete the combination by injecting random arguments of the relevant type". (This probably won't make sense unless you saw the "arithmetic test" motivating example.) And currying can't deal with this, as the *incomplete* combinations will have different types. But I suspect that Brandon's suggestion to use QuickCheck's Gen monad, could well help with this.