这个元组创作成语有没有名字？

Question

在Boost邮件列表中,@ LouisDionne最近发布了以下创建类似元组的实体的巧妙技巧:

#include <iostream>

auto list = [](auto ...xs) { 
    return [=](auto access) { return access(xs...); }; 
}; 

auto length = [](auto xs) { 
    return xs([](auto ...z) { return sizeof...(z); }); 
};

int main()
{
    std::cout << length(list(1, '2', "3")); // 3    
}

实例.

聪明之处在于listlambda采用可变参数列表作为输入,并返回lambda作为输出,将另一个lambda作用于其输入.类似地,lengthlambda是一个类似列表的实体,它将sizeof...向列表的原始输入参数提供可变参数运算符.在sizeof...操作上缠绕有拉姆达的内部,使得它可以被传递给list.

问题:这个元组创作成语是否有名称？也许来自函数式编程语言,其中更常用的是高阶函数.

Answer 1

我认为这是一个类似Monad的东西的微妙实现,特别是与延续monad相同的精神.

Monads是一种函数式编程结构,用于模拟计算的不同步骤之间的状态(请记住,函数式语言是无状态的).
monad所做的是链接不同的函数,创建一个"计算管道",其中每一步都知道计算的当前状态.

Monads有两个主要的pilars:

• 一个返回函数,它接受一个值并以Monad-ready形式返回它.
• 一个绑定函数,它接受Monad-ready值(从前一个管道步骤开始)并将其解包为原始值,以将值传递给下一步.

维基百科有关于monad的非常好的例子和解释.

让我重写给定的C++ 14代码:

auto list = []( auto... xs ) 
{ 
    return [=]( auto access ) { return access(xs...); };
};

我想在这里我们确定returnmonad 的功能:获取值并以Monadic方式返回它.具体来说,这个返回返回一个仿函数(在数学意义上,不是C++仿函数),它从"元组"类别变为可变参数包类别.

auto pack_size = [](auto... xs ) { return sizeof...(xs); };

pack_size只是一个正常的功能.它将在管道中用于做一些工作.

auto bind = []( auto xs , auto op ) 
{
    return xs(op);
};

并且length只是monad bind运算符附近的非泛型版本,运算符从前一个流水线步骤获取monadic值,并将其绕过指定的函数(函数真正完成工作).该功能是该计算步骤完成的功能.

最后你的电话可以改写为:

auto result = bind(list(1,'2',"3"), pack_size);

那么,这个元组创作成语的名称是什么？好吧,我认为这可以被称为" monad-like元组 ",因为它不完全是monad,但是元组表示和扩展以类似的方式工作,留在Haskell延续monad中.

编辑:更有趣

只是为了摆脱有趣的C++编程,我一直在探索这个类似Monad的东西.你可以在这里找到一些例子.

Answer 2

我会称这个成语元组继承器或更一般地称为monadic-continuator.它绝对是一个延续monad的实例.这里有关于C++程序员的continuation monad的精彩介绍.本质上,list上面的lambda取一个值(一个可变参数包)并返回一个简单的'continuator'(内部闭包).当给定可调用(被调用access)时,此继承器将参数包传递给它并返回可调用返回的任何内容.

借用FPComplete博客文章,延续器或多或少如下.

template<class R, class A>
struct Continuator {
    virtual ~Continuator() {}
    virtual R andThen(function<R(A)> access) = 0;
};

在Continuator上面的是抽象的-不提供一个实现.所以,这是一个简单的.

template<class R, class A>
struct SimpleContinuator : Continuator<R, A> {
    SimpleContinuator (A x) : _x(x) {}
    R andThen(function<R(A)> access) {
        return access(_x);
    }
    A _x;
};

在SimpleContinuator接受类型的一个值A,并将其传递到access时andThen被调用.list上面的lambda基本相同.它更通用.内部闭包不是单个值,而是捕获参数包并将其传递给access函数.整齐!

希望这能解释成为继承者意味着什么.但是成为一个单子是什么意思？这是一个很好的介绍使用图片.

我认为listlambda也是一个列表monad,它被实现为一个continuation monad.请注意,continuation monad是所有monad的母亲.即,你可以使用continuation monad实现任何monad.当然,列表monad并非遥不可及.

由于参数包很自然地是一个"列表"(通常是异构类型),因此它像列表/序列monad一样工作是有意义的.list上面的lambda是一种将C++参数包转换为monadic结构的非常有趣的方法.因此,操作可以一个接一个地链接.

length然而,上面的lambda有点令人失望,因为它打破了monad并且嵌套的lambda里面只返回一个整数.可以说有更好的方法来编写长度'getter',如下所示.

---- ----函子

在我们可以说列表lambda是monad之前,我们必须证明它是一个仿函数.即,必须为列表编写fmap.

上面的lambda列表作为参数包的仿函数的创建者 - 基本上它作为return.创建的functor保持参数包与自身(捕获),并允许'访问'它,只要你给一个接受可变数量的参数的可调用.请注意,callable称为EXACTLY-ONCE.

让我们为这样的仿函数写fmap.

auto fmap = [](auto func) { 
    return [=](auto ...z) { return list(func(z)...); };
};

函数的类型必须是(a - > b).即,在C++中说,

template <class a, class b>
b func(a);

fmap的类型fmap: (a -> b) -> list[a] -> list[b]就是说,在C++中,

template <class a, class b, class Func>
list<b> fmap(Func, list<a>);

即,fmap只是将list-of-a映射到list-of-b.

现在你可以做到

auto twice = [](auto i) { return 2*i; };
auto print = [](auto i) { std::cout << i << " "; return i;};
list(1, 2, 3, 4)
    (fmap(twice))
    (fmap(print)); // prints 2 4 6 8 on clang (g++ in reverse)

因此,它是一个算子.

- - 单子 - -

现在,让我们试着写一flatmap(又名bind,selectmany)

flatmap的类型是 flatmap: (a -> list[b]) -> list[a] -> list[b].

即,给定将a映射到list-of-b和list-of-a的函数,flatmap返回list-of-b.本质上,它从list-of-a中获取每个元素,在其上调用func,逐个接收(可能为空)list-of-b,然后连接所有list-of-b,最后返回最终列表-of-b.

这是list的flatmap实现.

auto concat = [](auto l1, auto l2) {
    auto access1 = [=](auto... p) {
      auto access2 = [=](auto... q) {
        return list(p..., q...);
      };
      return l2(access2);
    };
    return l1(access1);
};

template <class Func>
auto flatten(Func)
{
  return list(); 
}

template <class Func, class A>
auto flatten(Func f, A a)
{
  return f(a); 
}

template <class Func, class A, class... B>
auto flatten(Func f, A a, B... b)
{
  return concat(f(a), flatten(f, b...));
}

auto flatmap = [](auto func) {
  return [func](auto... a) { return flatten(func, a...); };
};

现在,您可以使用列表执行许多强大的操作.例如,

auto pair  = [](auto i) { return list(-i, i); };
auto count = [](auto... a) { return list(sizeof...(a)); };
list(10, 20, 30)
    (flatmap(pair))
    (count)
    (fmap(print)); // prints 6.

count函数是monad-perserving操作,因为它返回单个元素的列表.如果你真的想获得长度(没有包含在列表中),你必须终止monadic链并获得如下值.

auto len = [](auto ...z) { return sizeof...(z); }; 
std::cout << list(10, 20, 30)
                 (flatmap(pair))
                 (len);

如果完成,收集管道模式(例如filter,reduce)现在可以应用于C++参数包.甜!

---- Monad Laws ----

让我们确保listmonad满足所有三个monad定律.

auto to_vector = [](auto... a) { return std::vector<int> { a... }; };

auto M = list(11);
std::cout << "Monad law (left identity)\n";
assert(M(flatmap(pair))(to_vector) == pair(11)(to_vector));

std::cout << "Monad law (right identity)\n";
assert(M(flatmap(list))(to_vector) == M(to_vector));

std::cout << "Monad law (associativity)\n";
assert(M(flatmap(pair))(flatmap(pair))(to_vector) == 
       M(flatmap([=](auto x) { return pair(x)(flatmap(pair)); }))(to_vector));

所有断言都得到满足.

----收集管道----

虽然上面的"列表"lambda可证明是monad并且具有众所周知的'list-monad'的特征,但它是非常不愉快的.特别是,因为普通收集管道组合器的行为,例如filter(又名where)不符合共同的期望.

原因是C++ lambdas的工作原理.每个lambda表达式都会生成一个唯一类型的函数对象.因此,list(1,2,3)产生一个与之无关的类型list(1)和一个空列表,在这种情况下就是这样list().

where编译失败的直接实现,因为在C++中函数不能返回两种不同的类型.

auto where_broken = [](auto func) {
  return flatmap([func](auto i) { 
      return func(i)? list(i) : list(); // broken :-(
  }); 
};

在上面的实现中,func返回一个布尔值.它是一个谓词,表示每个元素的真或假.？:运算符无法编译.

因此,可以使用不同的技巧来继续收集管道.它们不是实际过滤元素,而是简单地标记为 - 这就是让它变得不愉快的原因.

auto where_unpleasant = [](auto func) {
  return [=](auto... i) { 
      return list(std::make_pair(func(i), i)...);
  }; 
};

该where_unpleasant干得不错,但令人不快...

例如,这是您可以过滤负面元素的方法.

auto positive = [](auto i) { return i >= 0; };
auto pair_print = [](auto pair) { 
  if(pair.first) 
     std::cout << pair.second << " "; 
  return pair; 
};
list(10, 20)
    (flatmap(pair))
    (where_unpleasant(positive))
    (fmap(pair_print)); // prints 10 and 20 in some order

----异类元组----

到目前为止,讨论的内容是同质元组.现在让我们将它推广到真正的元组.然而fmap,flatmap,where只需要一个回调拉姆达.为了提供多个lambdas,每个lambda都处理一种类型,我们可以重载它们.例如,

template <class A, class... B>
struct overload : overload<A>, overload<B...> {
  overload(A a, B... b) 
      : overload<A>(a), overload<B...>(b...) 
  {}  
  using overload<A>::operator ();
  using overload<B...>::operator ();
};

template <class A>
struct overload<A> : A{
  overload(A a) 
      : A(a) {} 
  using A::operator();
};

template <class... F>
auto make_overload(F... f) {
  return overload<F...>(f...);   
}

auto test = 
   make_overload([](int i) { std::cout << "int = " << i << std::endl; },
                 [](double d) { std::cout << "double = " << d << std::endl; });
test(10); // int 
test(9.99); // double    

让我们使用重载的lambda技术来处理异构元组继承器.

auto int_or_string = 
        make_overload([](int i) { return 5*i; },
                      [](std::string s) { return s+s; });
    list(10, "20")
        (fmap(int_or_string))
        (fmap(print)); // prints 2020 and 50 in some order

最后,直播示例