标签: imperative-programming

我开始学习ocaml,我非常欣赏语言中递归的力量.但是,我担心的一件事是堆栈溢出.

如果ocaml使用堆栈进行函数调用,它最终是否会溢出堆栈？例如,如果我有以下功能:

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

它必须最终导致堆栈溢出.如果我在c ++(使用递归)中做相同的事情,我知道它会溢出.

所以我的问题是,是否有内置的安全措施来防止函数式语言溢出堆栈？如果不是这样,它们是不是没那么有用,因为上面的求和算法,用带有for循环的过程样式编写,可以处理任何数字(不相关的整数溢出)？

我过去两个小时一直试图理解这个算法,但似乎无法理解.有人可以用容易理解的方式解释一下吗？

function lis_length(a)
    n := a.length
    q := new Array(n)
    for k from 0 to n:
        max := 0;
        for j from 0 to k, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 0 to n:
        if q[i] > max, then set max = q[i].
    return max;

关于函数式语言的解释,我有一个普遍的问题:

在运行时使用函数式语言与命令式语言(或者转向解释器)实际上是否有任何优势？

我看到的所有问题(例如这个)都没有真正解决这个问题,搜索充满了关于不同语言定义的争论.

编辑:剥离到我最终需要回答的唯一问题.

我有一个问题来比较两棵树.如下所示:

case class Node(elem:String, child:List[Node])

为了比较树的每个元素,我有以下功能:

def compare(n1:Node, n2:Node): Boolean {
   if(n1.elem == n2.elem){
      return compare(n1.child, n2.child)
   }
}

def compare(c1:List[Node], c2:List[Node]): Boolean {
    while (c1.notEmpty) {
       //filter, map etc call function above to compare the element recursively
    }
}

基本上算法是针对n1中的每个元素,我们正在检查n2中的匹配.我被告知这是非常必要的方式而不是功能方式.什么是实现这种行为的功能性方法.换句话说,在比较孩子列表时,我们如何删除while循环？

我正在寻找功能风格的算法(或这种算法的参数),这比命令式更快.

我喜欢功能代码,因为它具有表现力,而且比它的命令性吊坠更容易阅读.但我也知道这种表现力可能会花费运行时开销.并不总是由于尾递归等技术 - 但往往它们更慢.

虽然节目我不会去想的功能代码运行成本,因为现在的电脑速度非常快,发展的时间比运行时更为昂贵.此外,对我而言,可读性比性能更重要.然而,我的程序足够快,所以我很少需要以命令的方式解决问题.

有些算法在实践中应该以命令式方式(如排序算法)实现,否则在大多数情况下它们太慢或需要大量内存.在由于像模式匹配整个节目像写在功能语言解析器技术对比度可能多于一个的写入命令式语言的编译器,因为的可能性来优化代码快得多.

但是,是否有任何算法在功能样式上更快或者是否有可能设置这种算法的参数？

我有一个方法实现在命令式和功能性(我在这里尽我所能)的方式.该方法迭代ArrayBuffer [生物],计算每个生物的距离并返回最近或无(如果世界上没有生物,除了'this').

势在必行:

private def closestEnemy: Option[Creature] = {
  var closest: Option[Creature] = None
  var distanceToClosest = Int.MaxValue

  for(creature <- game.creatures if creature != this) {
    val distance = distanceTo(creature)

    if(distance < distanceToClosest) {
      closest = Some(creature)
      distanceToClosest = distance
    }
  }

  closest
}

功能:

private def closestEnemy: Option[Creature] =
  game.creatures filter { _ != this } map { creature => (creature, distanceTo(creature)) } match {
    case creaturesWithDistance if creaturesWithDistance.isEmpty => None
    case creaturesWithDistance => Some(creaturesWithDistance minBy { _._2 } …

函数式编程中的纯函数是没有副作用的函数.其中一个含义是它不能改变输入参数的值.这可以被视为内存利用的缺点吗？
例如,假设我有一个函数,它只需要一个列表并在其中添加另一个元素.在C++中,它可以很简单

void addElem(std::vector& vec, int a)
{
    vec.insert(a);
}

这个函数显然没有使用传递对象已经占用的大量内存.
但在Haskell中也会出现类似的情况.

addElem :: [Int] -> Int -> [Int] 
addElem xs a = xs ++ [a]

现在在这个计算中,因为xs没有改变它的值.所以我说的是,在某些时候,该函数将消耗xs的内存双倍大小,一个用于xs,另一个用于返回值.或者以某种方式延迟调用确保实际xs只通过在末尾添加一个元素才能返回？
我知道Monad是一种可以产生副作用的方法.但Monad可以用来简单地修改输入并返回它的值吗？
也可以将xs ++ [a]更改为:xs消耗更少的内存？

如何成功地抛弃函数的返回值并将其视为返回单元(显然是副作用).显而易见的方法是这样做:

let foo = begin
  some_ignored_thing ();
  actual_return
end

但是,编译器抱怨(带有警告)返​​回类型some_ignored_thing不是单位.

我可以创建自己的方法,例如:

let ignore a = ()

这看起来至少简洁并标记了某些事情正在发生,但是语言/ stdlib中是否有任何东西可以达到同样的效果？我原以为这是一个相对常见的用例.

我正在使用多个文件,我有一个可变字段的问题.在file1.ml中,我声明:

type mytype = {
     mutable numbers : int list;
}

所以,在file2.ml中,我有mytype类型的元素.但是,当我想做的时候:

myElement.numbers

返回以下错误:错误:未绑定的记录字段标签号.

谢谢,欢迎任何帮助.

因此,函数式语言中的模式匹配非常棒.我想知道为什么大多数命令式语言都没有实现这个功能？根据我的理解,Scala是唯一具有模式匹配的"主流"命令式语言.外壳/开关结构的功能不那么强大.

特别是,我感兴趣的是缺乏模式匹配是因为技术原因还是历史原因？