江苏龙网

  1. 首页 > 生活 > >

咋理解Boehm-Berarducci Encoding?

Boehm-Berarducci Encoding能将strictly positive的代数数据类型编码到System F中。举个在很多相关paper中很常见的例子：
data List a = Cons a (List a) | Nil-- Boehm-Berarducci Encodingtype List a = forall x . (a -\u0026gt; x -\u0026gt; x) -\u0026gt; x -\u0026gt; x这里定义了一个List，首先第一个通过algebraic data type的形式recursively的定义了List。第二个是将其编码成Boehm-Berarducci Encoding的形式。然后可以将具体的operation也进行编码：
-- Constructionfoo :: List Intfoo = Cons 0 (Cons 1 Nil)-- Boehm-Berarducci Encodingfoo :: List Intfoo :: \\cons nil -\u0026gt; cons 0 (cons 1 nil)-- Pattern Matchingmap :: (a -\u0026gt; b) -\u0026gt; List a -\u0026gt; List bmap f Nil = Nilmap f (Cons a l) = Cons (f a) (map f l)-- Boehm-Berarducci Encodingmap :: (a -\u0026gt; b) -\u0026gt; List a -\u0026gt; List bmap f l = \\cons nil -\u0026gt; l (\\a x -\u0026gt; cons (f a) x) nil 【咋理解Boehm-Berarducci Encoding?】 参考：
Boehm-Berarducci EncodingAn intermediate language for super-optimizing functional programs


    推荐阅读


    上一篇：怎样看待robocon2017国内某企业为部分参赛队提供3万元资金参赛支持可能是哪个企业

    下一篇：怎样评价第 8 代 Kindle（目前即将发布 Kindle Oasis）