标签: functional-programming

我在关于haskell和函数式编程的博客中经常阅读这个术语(特别是在sigfpe的博客中),但我不清楚这是什么意思.我大部分时间都不知道,但如果我知道,我可能会更好地理解文本.谷歌没有帮助我.我迷失在技术方面.

此外,世界的非技术含义("改变抽象具体")并没有帮助我理解在代码中实现某些东西的实际意义.

我对计算机科学概念有点慢,所以使用代码的实际例子会很好.:P

Edwin C. Brady撰写的关于Idris影响的"使用代数效应和依赖类型进行编程和推理"的论文包含(未引用的)声明:

尽管[效果和单子变换器]在功率上并不相同 - monad和monad变换器可以表达更多概念 - 但是捕获了许多常见的有效计算.

哪些例子可以通过monad变换器建模而不是效果？

我将在离散结构中教授低级课程.我选择了教科书" 离散结构,逻辑和可计算性",因为它包含有助于使用函数式编程语言实现的示例和概念.(我也认为这是一本很好的教科书.)

我想要一个易于理解的FP语言来说明DS概念以及学生可以使用的.大多数学生最多只能用一到两个学期的Java编程.在查看Scheme,Erlang,Haskell,Ocaml和SML之后,我已经确定了Haskell或Standard ML.由于下面列出的原因,我倾向于Haskell,但我喜欢那些活跃的程序员在一个或另一个的意见.

• Haskell和SML都具有模式匹配,这使得描述递归算法变得简单.
• Haskell具有很好的列表推导,可以很好地匹配这些列表以数学方式表达的方式.
• Haskell有懒惰的评价.非常适合使用列表推导技术构建无限列表.
• SML有一个真正的交互式解释器,可以在其中定义和使用函数.在Haskell中,函数必须在单独的文件中定义,并在交互式shell中使用之前进行编译.
• SML以易于理解的语法明确确认函数参数和返回类型.例如:val foo = fn:int*int - > int.Haskell隐含的咖喱语法有点迟钝,但并非完全陌生.例如:foo :: Int - > Int - > Int.
• Haskell默认使用任意精度的整数.它是SML/NJ中的外部库.并且SML/NJ默认将输出截断为70个字符.
• Haskell的lambda语法很微妙 - 它使用单个反斜杠.SML更明确.但是不确定我们是否会在这堂课中需要lambda.

从本质上讲,SML和Haskell大致相同.我倾向于Haskell,因为我喜欢Haskell中的列表理解和无限列表.但我担心Haskell紧凑语法中的大量符号可能会导致学生出现问题.从我收集到的关于SO的其他帖子开始,Haskell不建议初学者从FP开始.但我们不打算构建成熟的应用程序,只是尝试简单的算法.

你怎么看？

编辑:在阅读了一些很棒的回复后,我应该澄清一些我的要点.

在SML中,在解释器中定义函数和在外部文件中定义函数之间没有语法上的区别.假设您要编写阶乘函数.在Haskell中,您可以将此定义放入文件中并将其加载到GHCi中:

fac 0 = 1
fac n = n * fac (n-1)

对我来说,这很清楚,简洁,并且符合书中的数学定义.但是如果你想直接在GHCi中编写函数,你必须使用不同的语法:

let fac 0 = 1; fac n = n * fac (n-1)

在使用交互式口译员时,从教学角度来看,当学生在文件和命令行中使用相同的代码时,非常非常方便.

通过"显式确认函数",我的意思是在定义函数时,SML立即告诉您函数的名称,参数的类型和返回类型.在Haskell中你必须使用:type命令,然后你会得到一些有点令人困惑的咖喱符号.

关于Haskell的一个更酷的事情 - 这是一个有效的函数定义:

fac 0 = 1
fac (n+1) = (n+1) * fac n

同样,这与他们可能在教科书中找到的定义相匹配.在SML中无法做到这一点!

就像背景一样,我知道Fisher-Yates完美的洗牌.它的O(n)复杂性和保证的一致性是一个很好的混乱,我不会使用它...在一个允许就地更新数组的环境中(所以在大多数情况下,如果不是全部,命令式编程环境).

可悲的是,函数式编程世界并没有让你访问可变状态.

然而,由于Fisher-Yates,我没有很多关于如何设计改组算法的文献.完全解决这个问题的几个地方之前做了这么简单的说法,实际上,"所以这里是Fisher-Yates,这是你需要知道的所有洗牌".最后,我必须提出自己的解决方案.

我想出的解决方案是这样的,可以随机播放任何数据列表:

• 如果列表为空,则返回空集.
• 如果列表包含单个项目,则返回该单个项目.
• 如果列表非空,则使用随机数生成器对列表进行分区,并将算法递归地应用于每个分区,然后汇总结果.

在Erlang代码中,它看起来像这样:

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(如果这看起来像是一种疯狂的快速排序,那么,基本上就是这就是它.)

所以这就是我的问题:同样的情况使得找到非Fisher-Yates 的改组算法变得困难,这使得找到分析混洗算法的工具同样困难.在分析PRNG的均匀性,周期性等方面,我可以找到很多文献,但没有关于如何分析洗牌的大量信息.(事实上​​,我在分析shuffle时发现的一些信息是完全错误的 - 很容易通过简单的技术欺骗.)

所以我的问题是:我如何分析我的改组算法(假设那里的random:uniform()调用可以生成具有良好特性的适当随机数)？我可以使用哪些数学工具来判断,在1 ... 100的整数列表中,是否有100,000次洗牌运行给了我合理的改组结果？我已经做了一些我自己的测试(例如,比较增量到shuffles中的减量),但我想知道更多.

如果对该混洗算法本身有任何了解,也会受到重视.

我想通过使用该map()函数来过滤项目数组.这是一段代码:

var filteredItems = items.map(function(item)
{
    if( ...some condition... )
    {
        return item;
    }
});

问题是过滤掉的项目仍然使用数组中的空间,我想完全消除它们.

任何的想法？

编辑:谢谢,我忘了filter(),我想要的实际上是filter()一个map().

EDIT2:感谢您指出map()并且filter()并未在所有浏览器中实现,尽管我的特定代码并不打算在浏览器中运行.

我一次又一次地听到,我正在努力理解并验证FP和OO是正交的想法.

首先,2个概念的正交意味着什么？

FP尽可能地鼓励不变性和纯度,而OO似乎是为状态和变异而构建的 - 一个有点组织的命令式编程版本？我意识到对象可以是不可变的,但OO似乎意味着状态/改变我.

它们看起来像是对立的.这对他们的正交性有何影响？

像Scala这样的语言可以很容易地执行OO和FP,这是否会影响这两种方法的正交性？

我是Haskell的新手,我正在阅读有关仿函数和应用函子的内容.好吧,我理解仿函数以及如何使用它们,但我不明白为什么应用仿函数是有用的以及我如何在Haskell中使用它们.你能用一个简单的例子向我解释为什么我需要应用仿函数吗？

给定数据结构规范,例如具有已知复杂性边界的纯函数映射,必须在若干实现之间进行选择.有一些关于如何选择正确的民间传说,例如红黑树被认为通常更快,但AVL树在工作负载上具有更好的性能和许多查找.

1. 是否有关于这种知识的系统性介绍(发表的论文)(与集合/地图相关)？理想情况下,我希望看到对实际软件进行统计分析.例如,它可能得出结论,有N种典型的地图用法,并列出每种地图的输入概率分布.

2. 是否有系统基准测试地图并设置不同输入分布的性能？

3. 是否存在使用自适应算法根据实际使用情况更改表示的实现？

你真的"试过"(意味着编程,而不只是阅读一篇文章)Erlang并决定反对它的项目？如果是这样,为什么？此外,如果您选择回到旧语言,或使用其他功能语言,如F#,Haskell,Clojure,Scala或其他类似的东西,那么这也很重要,并说明原因.

在Python中,我想编写一个make_cylinder_volume(r)返回另一个函数的函数.返回的函数应该可以使用参数调用h,并返回具有高度h和半径的圆柱体积r.

我知道如何从Python中的函数返回值,但是如何返回另一个函数？