Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Реализация fold и списков на HN

В значительной степени на нововведения в HN повлиял следующий тестовый пример-use case. Это довольно наивная реализация fold шаблоном C++ и реализация абстрактного типа данных списка (без операций конструирования, т.к. их fold не использует) поверх ASCIIZ-строк.
template<typename F, typename V, typename L>
V fold (F f, V v, L l) 
{
   while (!isNil(l))
   {
      ret = f(ret, head(l));    
      l = tail(l);
   }
   return ret;
}
char head(const char * _this)
{
   return *_this;
}

const char* tail(const char * _this)
{
   return _this + 1;
}

bool isNil(const char * _this)
{
   return *_this == '\0';
}

Сравните c реализацией fold и isNil на HN:
fold :: forall f v l . f -> v -> l -> v
fold f v l = 
{  
   while (not (isNil l)) 
   {
       v := f v (head l)
       l := tail l
   }
   v
}
isNil :: const char * -> bool
isNil _this = == (deref _this) '\0'
Во-первых, соответствие достаточно прямолинейное, что существенно упрощает компилятор.

Во-вторых, производительность кода, сгенерированного компилятором С++, будет идентична производительности кода без ФВП, написанного вручную, если все функции (включая аргумент f функции fold) проинлайнятся.
Tags: compiler design, hn0
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments