使用循环将C函数转换为Haskell

Question

我试图推理如何将命令式样式程序转换为像Haskell这样的功能性程序.

功能是:

void calcPerim(point polycake[], int v, int y, double *perim1, double *perim2){
    int next = 0;
    int index = 0;
    point points[2];
    *perim1 = 0.0;
    *perim2 = 0.0;

    for(int i = 0; i < v; i++)
    {
        next = (i + 1) % v;
        if(polycake[i].y < y && polycake[next].y < y)
            (*perim1) += distance(polycake[i], polycake[next]);
        else if(polycake[i].y > y && polycake[next].y > y)
            (*perim2) += distance(polycake[i], polycake[next]);
        else
        {
            points[index] = intersectPoint(polycake[i], polycake[next], y);
            if(polycake[i].y < y)
            {
                (*perim1) += distance(polycake[i], points[index]);
                (*perim2) += distance(polycake[next],points[index]);
            }
            else
            {
                (*perim2) += distance(polycake[i], points[index]);
                (*perim1) += distance(polycake[next],points[index]);
            }
            index++;
        }
    }

    (*perim1) += distance(points[0], points[1]);
    (*perim2) += distance(points[0], points[1]);
}

我发现在某些情况下,当它同时更新两个变量时,我很难理解如何将其变为功能方法.将它转换为递归以传入元组时,它会有意义(perim1, perim2)吗？

Answer 1

最好不要直接转换为Haskell,而是首先转换为C++,这已经允许您以更加实用的方式构建它.

首先,正如Cirdec评论的那样,这个函数并没有真正perim1作为参数 - 这些是Fortran人们会说的"输出参数",即它们真的是结果.此外,v参数似乎基本上只是输入数组的长度.所以在C++中你可以把它减少到:

std::pair<double, double> calcPerim(std::vector <point> polycake, int y){
   double perim1 = 0, perim2 = 0;
   ...
   return std::make_pair(perim1, perim2);
}

现在,你有这个变异for循环.在函数式语言中,一般方法是用递归替换它.为此,您需要创建所有可变状态变量函数参数.这包括i,index,points和perim蓄电池(所以他们回来了,在某种程度上......但现在作为输入参数).您不需要next(在每次迭代中无论如何都是从头开始重新计算).

std::pair<double, double> calcPerim_rec
                   ( std::vector<point> polycake, int y
                   , int i, int index, std::array<point,2> points
                   , double perim1Acc, double perim2Acc ){
   ...
}

......被...使用

std::pair<double, double> calcPerim(std::vector<point> polycake, int y){
   return calcPerim_rec(polycake, y, 0, 0, {}, 0, 0);
}

递归函数看起来与原始循环体非常相似; 你只需要说出结束条件:

std::pair<double, double> calcPerim_rec
                   ( std::vector<point> polycake, int y
                   , int i, int index, std::array<point,2> points
                   , double perim1Acc, double perim2Acc ){
    if (i < polycake.length()) {
        int next = (i + 1) % polycake.length();
        if(polycake[i].y < y && polycake[next].y < y)
            perim1Acc += distance(polycake[i], polycake[next]);
        else if(polycake[i].y > y && polycake[next].y > y)
            perim2Acc += distance(polycake[i], polycake[next]);
        else
        {
            points[index] = intersectPoint(polycake[i], polycake[next], y);
            if(polycake[i].y < y)
            {
                perim1Acc += distance(polycake[i], points[index]);
                perim2Acc += distance(polycake[next],points[index]);
            }
            else
            {
                perim2Acc += distance(polycake[i], points[index]);
                perim1Acc += distance(polycake[next],points[index]);
            }
            ++index;
        }
        ++i;
        return calcPerim_rec
                 ( polycake, y, i, index, points, perim1Acc, perim2Acc );
    } else {
       perim1Acc += distance(points[0], points[1]);
       perim2Acc += distance(points[0], points[1]);
       return std::make_pair(perim1Acc, perim2Acc);
    }
}

仍然有相当多的可变性,但是我们已经将它封装在递归函数调用的局部变量上,而不是在循环执行期间存在的变量.并且每个变量只更新一次,然后是递归调用,因此您可以跳过变异并简单地将值加上更新传递给递归调用:

std::pair<double, double> calcPerim_rec
                   ( std::vector<point> polycake, int y
                   , int i, int index, std::array<point,2> points
                   , double perim1Acc, double perim2Acc ){
    if (i < polycake.length()) {
        int next = (i + 1) % polycake.length();
        if(polycake[i].y < y && polycake[next].y < y)
            return calcPerim_rec
             ( polycake, y, i+1, index, points
             , perim1Acc + distance(polycake[i], polycake[next])
             , perim2Acc
             );
        else if(polycake[i].y > y && polycake[next].y > y)
            return calcPerim_rec
             ( polycake, y, i+1, index, points
             , perim1Acc
             , perim2Acc + distance(polycake[i], polycake[next])
             );
        else
        {
            points[index] = intersectPoint(polycake[i], polycake[next], y);
            if(polycake[i].y < y)
            {
                return calcPerim_rec
                 ( polycake, y, i+1, index+1
                 , points
                 , perim1Acc + distance(polycake[i], points[index])
                 , perim2Acc + distance(polycake[next],points[index])
                 );
            }
            else
            {
                return calcPerim_rec
                 ( polycake, y, i+1, index+1
                 , points
                 , perim1Acc + distance(polycake[i], points[index])
                 , perim2Acc + distance(polycake[next],points[index])
                 );
            }
        }
    } else {
       return std::make_pair( perim1Acc + distance(points[0], points[1])
                            , perim2Acc + distance(points[0], points[1]) );
    }
}

嗯,相当多的尴尬传递参数,我们仍然有一个变异points- 但实质上,代码现在可以转换为Haskell.

import Data.Vector (Vector, (!), length) as V

calcPerim_rec :: Vector Point -> Int -> Int -> Int -> Int -> [Point] -> (Double, Double) -> (Double, Double)
calcPerim_rec polycake y i index points (perim1Acc, perim2Acc)
 = if i < V.length polycake
    then
     let next = (i + 1) `mod` V.length polycake
     in if yCoord (polycake!i) < y && yCoord (polycake!next) < y
         then calcPerim_rec polycake v y (i+1) index points
                (perim1Acc + distance (polycake!i) (polycake!next)
                perim2Acc
         else
          if yCoord (polycake!i) > y && yCoord (polycake!next) > y)
           then calcPerim_rec polycake v y (i+1) index points
                     perim1Acc
                     (perim2Acc + distance (polycake!i) (polycake!next))
           else
            let points' = points ++ [intersectPoint (polycake!i) (polycake!next) y]
            in if yCoord (polycake!i) < y
                then calcPerim_rec polycake v y (i+1) (index+1)
                       points'
                       (perim1Acc + distance (polycake!i) (points!!index))
                       (perim2Acc + distance (polycake!next) (points!!index))
                else calcPerim_rec polycake v y (i+1) (index+1)
                       points'
                       (perim1Acc + distance (polycake!i) points!!index))
                       (perim2Acc + distance (polycake!next) points!!index))
    else ( perim1Acc + distance (points!!0) (points!!1)
         , perim2Acc + distance (points!!0) (points!!1) )

这里有很多可以在风格上进行改进,但它本质上应该起作用.

实际上使其成为惯用语的首要好处是尝试摆脱指数.在Haskell中强烈避免使用索引,并且在正确使用列表而不是数组时通常可以避免使用索引.