小编ice*_*man的帖子

我觉得我忽略了一些完全明显的东西,但是使用无点符号来组成二元函数和一元函数的正确方法(如果有的话)是什么？例如,以下代码编译:

sortedAppend :: (Ord a) -> [a] -> [a] -> [a]
sortedAppend xs ys = sort $ xs ++ ys

但以下代码无法编译:

sortedAppend :: (Ord a) -> [a] -> [a] -> [a]
sortedAppend = sort . (++)

难道我们能够组成(++)有sort(按顺序如上图所示)？如果是这样,怎么样？

以下代码是LYAH的逐字编译,无法编译.代码和编译时错误包括在下面.在LYAH页面上,代码在页面下方约15%,yay emacs浏览器:)

有什么想法吗？我忽略了一些完全明显的东西吗

(尽管后期标题相似,但我认为我的问题与此不同.)

这是代码(在我命名的文件中testcopy.hs)

import Control.Monad.Writer

logNumber :: Int -> Writer [String] Int
logNumber x = Writer (x, ["Got number: " ++ show x])

multWithLog :: Writer [String] Int
multWithLog = do
    a <- logNumber 3
    b <- logNumber 5
    return (a*b)

这是编译时错误:

Prelude> :l testcopy.hs
[1 of 1] Compiling Main             ( testcopy.hs, interpreted )
testcopy.hs:4:15:
    Not in scope: data constructor `Writer'
    Perhaps you meant `WriterT' (imported from Control.Monad.Writer)
Failed, modules loaded: none.

有人可以帮助我理解Wadler题为" 理解Monads " 的论文中的以下定义吗？(摘录自第3.2节/第9页,即"Strictness Monad"小节.)

有时需要在惰性函数程序中控制评估顺序.这通常通过可计算函数strict来实现,定义为

严格 f x =如果x ≠⊥则f x否则⊥.

在操作上,严格 ˚F X是通过首先减少降低X弱头正常形式(WHNF),然后还原应用˚F X.或者,可以安全地并行减少x和f x,但在x处于WHNF 之前不允许访问结果.

在论文中,我们还没有看到使用由两条垂直线组成的符号(不确定它叫什么)所以它有点无处不在.

鉴于Wadler继续说"我们将使用[严格]理解来控制懒惰程序的评估",这似乎是一个非常重要的概念.

TL; DR:
如何在返回类型中编写多态的函数？我正在练习,其中任务是写一个函数,它是能够分析的String,并根据其内容,生成或者是Vector [Int],Vector [Char]或Vector [String].

更长版本:
以下是一些预期函数的行为示例:

• 该字符串"1 2\n3 4"将生成一个Vector [Int]由两个列表组成的字符串:[1,2]和[3,4].

• 该字符串"'t' 'i' 'c'\n't' 'a' 'c'\n't' 'o' 'e'"将生成一个Vector [Char](即,由列表组成"tic","tac"和"toe").

• 该字符串"\"hello\" \"world\"\n\"monad\" \"party\""将生成一个Vector [String](即,["hello","world"]和["monad","party"]).

错误检查/异常处理不是此特定练习的关注点.在这个阶段,所有的测试都是纯粹的,即,这不是IOmonad 的范畴.

到目前为止我所拥有的:

我有一个函数(和新的数据类型),它能够对字符串进行分类.我也有函数(每个函数一个Int,Char和String),可以将字符串转换为必要的Vector.

我的问题:如何将这三个转换函数组合成一个函数？

我尝试过的:

• (如果我将三个转换函数填充到单个函数中(即,使用case..of结构来VectorType对字符串进行模式匹配),显然不会进行类型检查.

• 我尝试创建一个Vectorable类并为每种类型定义一个单独的实例; …

TL; DR:基于下面的Haskell代码及其相关的分析数据,我们可以得出哪些结论可以让我们修改/改进它,这样我们可以缩小性能差距,而不是用命令式语言编写的相同算法(即C++/Python/C#但具体语言不重要)？

背景

我写了下面一段代码作为一个流行网站上的问题的答案,其中包含许多编程和/或数学性质的问题.(您可能听说过这个网站,其名称由某些人发音为"oiler",其他人则称为"yoolurr".)由于下面的代码是其中一个问题的解决方案,我故意避免提及该网站的任何内容.名称或问题中的任何特定术语.那就是说,我说的是问题一百零三.

(事实上​​,我在常驻Haskell向导的网站论坛中看到了很多解决方案:P)

为什么我选择分析此代码？

这是第一个问题(在所说的网站上),我遇到了Haskell代码与C++/Python/C#代码之间的性能差异(以执行时间衡量)(当两者都使用类似的算法时).事实上,所有这些问题(迄今为止;我已经完成了大约100个问题但不是顺序问题)的情况就是优化的Haskell代码与最快的C++解决方案并驾齐驱,其中包括其他条件.算法,当然.

但是,论坛中针对此特定问题的帖子表明,这些其他语言中的相同算法通常最多需要一到两秒钟,最长需要10-15秒(假设相同的起始参数;我忽略了非常天真的算法需要2-3分钟+).相比之下,下面的Haskell代码在我的(正常)计算机上需要约50秒(禁用分析;启用分析后,需要约2分钟,如下所示;注意:编译时执行时间相同-fllvm).规格:i5 2.4ghz笔记本电脑,8GB RAM.

为了努力学习Haskell,它可以成为命令式语言的可行替代品,我解决这些问题的目的之一是学习编写尽可能具有与那些命令式语言相同的性能的代码. .在这种情况下,我仍然认为这个问题尚未解决(因为性能差异大约为25倍!)

到目前为止我做了什么？

除了简化代码本身(尽我所能)的明显步骤之外,我还执行了"真实世界Haskell"中推荐的标准分析练习.

但是我很难得出结论,告诉我需要修改哪些部分.这就是我希望人们可以提供一些指导的地方.

问题描述:

我将在上述网站上向您推荐问题一百零三的网站,但这里有一个简短的总结:目标是找到一组七个数字,这样任何两个不相交的子组(该组)满足以下两个属性(我试图避免因上述原因而使用'set'一词......):

• 没有两个小组总和相同的数量
• 具有更多元素的子组具有更大的和(换句话说,最小的四个元素的总和必须大于最大的三个元素的总和).

特别是,我们试图找到具有最小总和的七个数字组.

我的(无可否认的是弱势)观察

一个警告:其中一些评论可能完全错误但我想至少根据我在Real World Haskell中读到的内容以及SO上的其他与分析相关的帖子来解释分析数据.

• 确实存在效率问题,因为三分之一的时间用于垃圾收集(37.1%).第一个数据表显示堆中分配了~172gb,这看起来很糟糕......(也许有更好的结构/功能用于实现动态编程解决方案？)
• 毫不奇怪,绝大多数(83.1%)的时间用于检查规则1:(i)value子函数中的41.6%,其确定填充动态编程("DP")表的值,(ii)29.1%在table函数中,它生成DP表和(iii)rule1函数中的12.4%,它检查生成的DP表以确保给定的总和只能以一种方式计算(即,从一个子组).
• 但是,我确实发现令人惊讶的是,value相对于table和rule1函数花费了更多的时间,因为它是三个中唯一没有构造数组或通过大量元素过滤的函数(它实际上只执行O (1)查找并在Int类型之间进行比较,您认为这些类型相对较快.所以这是一个潜在的问题领域.也就是说,该value功能不太可能推动高堆分配

坦率地说,我不确定如何制作三张图表.

堆配置文件图表(即下面的第一个字符):

• 老实说,我不确定标记为红色区域的是什么Pinned.有意义的是,该dynamic函数具有"尖峰"内存分配,因为每次construct函数生成满足前三个条件的元组时都会调用它,并且每次调用它时,它都会创建一个相当大的DP数组.此外,我认为存储元组(由构造生成)的内存分配在程序过程中不会是平坦的.
• 在澄清"固定"红色区域时,我不确定这个区域告诉我们什么有用.

按类型分配和按构造函数分配:

• 我怀疑ARR_WORDS(根据GHC文档表示ByteString或未装箱的数组)表示DP阵列构造的低级执行(在table函数中).坚果我不是百分百肯定.
• 我不确定FROZEN和STATIC指针类别对应的是什么.
• 就像我说的那样,我真的不确定如何解释图表,因为没有任何事情像我一样跳出来(对我而言).

代码和分析结果

不用多说,这里是带有解释我的算法的注释的代码.我试图确保代码不会从代码框的右侧运行 - 但是一些注释确实需要滚动(抱歉).

{-# LANGUAGE NoImplicitPrelude #-}
{-# …

我希望有人可以帮助我理解为什么以下代码生成下面的输出.代码来自Simon Marlow的书中的Concurrency章节(链接如下).

基于各种函数的描述,我假设第二个putMVar函数应该被阻塞,因为(i)两个putMVar函数都是同一个线程的一部分,并且(ii)已经分配了一个值.显然情况并非如此.很高兴在这里了解"引擎盖下"发生了什么.

(注意:本书使用do符号,但我更喜欢>>=符号,因为我认为它更直接 - 因此下面的代码版本.)

链接到书

import Control.Concurrent

main :: IO ()
main = newEmptyMVar >>=
       \m -> forkIO (putMVar m 'x' >>= \_ -> putMVar m 'y') >>=
             \_ -> takeMVar m >>=
                   print >>=
                   \_ -> takeMVar m >>=
                         print

输出上面的代码:

% ./mvar2
'x'
'y'

我正在审查一些代码,并遇到了以下gem,我下注的是pointfree输出的复制粘贴:

(我认为以下内容比通常foo/ bar对于这个特定问题更合适:P)

import Control.Monad (liftM2)

data Battleship = Battleship { x :: Int
                             , y :: Int
                             } deriving Show

placeBattleship :: Int -> Int -> Battleship
placeBattleship x' y' = Battleship { x = x', y = y' }

coordinates :: Battleship -> (Int, Int)
coordinates = liftM2 (,) x y

有人会善意地解释简化所需的步骤:

(i)coordinates b = (x b, y b)

到:

(ii)coordinates = liftM2 (,) x y？

特别是,我对使用有点困惑,liftM2因为我甚至不知道monad潜伏在后台.

我知道(i)也可以表示为: …

来自Haskell n00b的另一个问题.

我正在比较Project Euler网站上用于解决问题#14的各种方法的效率.特别是,我希望能够更好地理解驱动评估时间差异的因素,以解决问题的四种(略微)不同方法.

(问题#14的描述和各种方法如下.)

首先,快速概述问题#14.它与"Collat​​z数字"有关(即,与我上一篇文章相同的编程练习,探讨了Haskell的不同方面).给定整数的Collat​​z数等于该整数的Collat​​z序列的长度.整数的Collat​​z序列计算如下:序列中的第一个数字("n0")是整数本身; 如果n0是偶数,则序列中的下一个数字("n1")等于n/2; 如果n0是奇数,那么n1等于3*n0 + 1.我们继续递归地扩展序列,直到我们到达1,此时序列结束.例如,5的折叠序列是:{5,16,8,4,2,1}(因为16 = 3*5 + 1,8 = 16/2,4 = 8/2,......).

问题14要求我们找到具有最大Collat​​z数的1,000,000以下的整数.为此,我们可以考虑一个函数"collat​​z",当传递一个整数"n"作为参数时,返回n以下具有最大Collat​​z数的整数.换句话说,p 1000000为我们提供了问题#14的答案.

出于本练习的目的(即,了解评估时间的差异),我们可以考虑Haskell版本的'collat​​z',它们在两个维度上有所不同:

(1)实现:我们是否将Collat​​z数据的数据集(将为所有整数1..n生成)作为列表或数组存储？我称之为"实现"维度,即函数的实现是"列表"或"数组".

(2)算法:我们是否通过扩展Collat​​z序列直到它完成(即直到我们达到1)来计算任何给定整数n的Collat​​z数？或者我们是否只延伸序列,直到我们达到小于n的数字k(此时我们可以简单地使用我们已经计算过的k的Collat​​z数)？我将其称为"算法"维度,即函数的算法是"完整"(计算每个整数的Collat​​z数)或"部分".后者显然需要更少的操作.

以下是"collat​​z"函数的四个可能版本:array/partial,list/partial,array/complete和list/complete:

import Data.Array ( (!) , listArray , assocs )
import Data.Ord ( comparing )
import Data.List ( maximumBy )

--array implementation; partial algorithm (FEWEST OPERATIONS)
collatzAP x = maximumBy (comparing snd) $ assocs a where
    a = listArray (0,x) (0:1:[c n n | n <- [2..x]])
    c n i = let z = if even i …

TL;DR：我如何使用findinMakefile来识别相关的源文件（例如，所有.c文件）？我知道如何使用 awildcard但我无法find开始工作。

更长的版本： 我将 aMakefile作为共享库练习的一部分；我注意到，当我使用以下几行为.c我的共享库指定源文件和目标文件（即文件）时，运行make( gcc fatal error: no input files)后出现错误：

SRC=$(find src/ -maxdepth 1 -type f -regex ".*\.c")
OBJ=$(patsubst %.c,%.o,$(SRC))
*rest-of-makefile*

但是，当我使用wildcard而不是find：

SRC=$(wildcard src/*.c)
OBJ=$(patsubst %.c,%.o,$(SRC))
*rest-of-makefile*

（作为参考，下面包括确认该find命令在从 shell 运行时确实返回了预期的文件。）

使用find命令（在 my 中Makefile）搜索我的源文件（如果可能的话）的正确语法是什么？

（为什么我更喜欢使用 find？：我喜欢这样一个事实，即我可以find通过从 shell 运行命令来快速复查语句的结果；我不能用 来做到这一点wildcard。另外，我想依靠如果可能，在正则表达式上。）

作为参考，下面是相关的树结构。正如您所看到的（从下面的第二个代码块），运行findMakefile 中指定的命令（即，从上面）确实返回了预期的文件 ( src/libex29.c)。换句话说，上述问题不是因为find选项或正则表达式中的语法问题。 …

我做了一些99 Haskell Problems之前的练习，我认为练习 27（“编写一个函数来枚举可能的组合”）很有趣，因为它是一个简单的概念，并且适用于多种实现。

我对相对效率很好奇，所以我决定运行几个不同的实现 - 结果在下表中。（参考：在 VirtualBox 上运行的 LXDE (Ubuntu 14.04) 中的 Emacs bash ansi-term；Thinkpad X220；8gb RAM，i5 64bit 2.4ghz。）

特尔；博士：

(i) 为什么组合生成技术 #7 和 #8（来自下表；代码包含在帖子底部）比其他技术快得多？
(ii) 另外，该Bytes栏中的数字实际上代表什么？

(i) 这很奇怪，因为函数 #7 通过过滤 powerset（比组合列表大 waaaay）来工作；我怀疑这是工作中的懒惰，即这是最有效地利用我们只要求列表长度而不是列表本身这一事实的函数。（此外，它的“内存使用率”低于其他函数，但话说回来，我不确定正在显示什么与内存相关的统计数据。）

关于功能#8：感谢Bergi 的快速实现，并感谢user5402 建议添加。仍然试图将我的领先优势围绕在这个速度差异上。

(ii)Bytes列中的数字是GHCi运行:set +s命令后上报的；它们显然不代表最大内存使用量，因为我只有 ~25gb 的 RAM + 可用 HD 空间。）？

代码：

import Data.List

--algorithms to generate combinations
--time required to compute the following: length $ 13 "abcdefghijklmnopqrstuvwxyz"

--(90.14 secs, 33598933424 bytes)
combDC1 :: (Eq a) => …