Joachim Breitner | 20 Jan 10:57 2013
Picon

Inferring rewrite rules for higher order functions

Dear list,

with rewrite rules I can tell the compiler to replace "map id" by "id",
but I still have to write that rule by hand.

Does anyone of you know about research into inferring such a rewrite
rule automatically? I could imagine that for a function of type "f ::
some -> args -> T a -> T b" and not-too-bad type constructors T it might
be possible under what conditions on "some" and "args" infer when "f
arg1 arg2 = id" holds, and if the conditions are fulfilled by functions
like "id", generate a rewrite rule "f id id = id" automatically.

Thanks,
Joachim
--

-- 
Joachim "nomeata" Breitner
  mail <at> joachim-breitner.de  |  nomeata <at> debian.org  |  GPG: 0x4743206C
  xmpp: nomeata <at> joachim-breitner.de | http://www.joachim-breitner.de/

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Jan Stolarek | 20 Jan 11:21 2013
Picon

Re: Inferring rewrite rules for higher order functions

The only paper that comes to my mind is Wadler's "Theorems for free". It's an old one and not 
exactly about rewrite rules, but it may be a good starting point.

Janek
Ramana Kumar | 20 Jan 15:13 2013
Picon
Picon

Re: Inferring rewrite rules for higher order functions

Work on deforestation might also be relevant.


On Sun, Jan 20, 2013 at 9:57 AM, Joachim Breitner <mail <at> joachim-breitner.de> wrote:
Dear list,

with rewrite rules I can tell the compiler to replace "map id" by "id",
but I still have to write that rule by hand.

Does anyone of you know about research into inferring such a rewrite
rule automatically? I could imagine that for a function of type "f ::
some -> args -> T a -> T b" and not-too-bad type constructors T it might
be possible under what conditions on "some" and "args" infer when "f
arg1 arg2 = id" holds, and if the conditions are fulfilled by functions
like "id", generate a rewrite rule "f id id = id" automatically.

Thanks,
Joachim
--
Joachim "nomeata" Breitner
  mail <at> joachim-breitner.de  |  nomeata <at> debian.org  |  GPG: 0x4743206C
  xmpp: nomeata <at> joachim-breitner.de | http://www.joachim-breitner.de/


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane