- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
在代码审查中,我回答了一个关于 naive Haskell fizzbuzz solution 的问题。通过建议 iterates forward 的实现,避免了增加素数的二次成本和(几乎)完全丢弃模除法。这是代码:
fizz :: Int -> String
fizz = const "fizz"
buzz :: Int -> String
buzz = const "buzz"
fizzbuzz :: Int -> String
fizzbuzz = const "fizzbuzz"
fizzbuzzFuncs = cycle [show, show, fizz, show, buzz, fizz, show, show, fizz, buzz, show, fizz, show, show, fizzbuzz]
toFizzBuzz :: Int -> Int -> [String]
toFizzBuzz start count =
let offsetFuncs = drop (mod (start - 1) 15) fizzbuzzFuncs
in take count $ zipWith ($) offsetFuncs [start..]
Data.List.unfoldr
重写它。 .
unfoldr
version 是对这段代码的明显、简单的修改,所以我不会在这里输入它,除非寻求回答我的问题的人坚持认为这很重要(代码审查中的 OP 没有剧透)。但我确实对
unfoldr
的相对效率有疑问。与
zipWith
相比的解决方案一。虽然我不再是 Haskell 新手,但我也不是 Haskell 内部结构方面的专家。
unfoldr
解决方案不需要
[start..]
无限列表,因为它可以简单地从
start
展开.我的想法是
zipWith
解决方案不会记住 [start..]
的每个连续元素正如它所要求的那样。每个元素都被使用和丢弃,因为没有保留对 [start..] 头部的引用。所以没有比 unfoldr
更多的内存消耗。 . unfoldr
性能的担忧最近的补丁使其始终内联,这是在我尚未达到的水平上进行的。 unfoldr
用于生成序列似乎是一件很自然的事情,即使其他解决方案更具表现力。我只知道我需要更多地了解它的实际性能。 (出于某种原因,我发现
foldr
在该级别上更容易理解)
unfoldr
对
Maybe
的使用是我什至开始调查该问题之前发生的第一个潜在性能问题(也是我完全理解的优化/内联讨论的唯一一点)。所以我可以不用担心
Maybe
马上(鉴于 Haskell 的最新版本)。
最佳答案
作为负责 zipWith
的最近实现变化的人和 unfoldr
,我想我可能应该尝试一下。我不能那么容易地比较它们,因为它们是非常不同的功能,但我可以尝试解释它们的一些属性和变化的意义。unfoldr
内联
旧版unfoldr
(在 base-4.8
/GHC 7.10 之前)在顶层是递归的(它直接调用自身)。 GHC 从不内联递归函数,所以 unfoldr
从未内联。结果,GHC 无法看到它如何与传递的函数进行交互。最令人不安的影响是传入的函数类型为 (b -> Maybe (a, b))
。 , 实际上会产生 Maybe (a, b)
值,分配内存来保存 Just
和 (,)
构造函数。通过重组 unfoldr
作为“worker”和“wrapper”,新代码允许 GHC 内联它并(在许多情况下)将它与传入的函数融合,因此额外的构造函数被编译器优化剥离。
例如,在 GHC 7.10 下,代码
module Blob where
import Data.List
bloob :: Int -> [Int]
bloob k = unfoldr go 0 where
go n | n == k = Nothing
| otherwise = Just (n * 2, n+1)
ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures
编译导致核心
$wbloob :: Int# -> [Int]
$wbloob =
\ (ww_sYv :: Int#) ->
letrec {
$wgo_sYr :: Int# -> [Int]
$wgo_sYr =
\ (ww1_sYp :: Int#) ->
case tagToEnum# (==# ww1_sYp ww_sYv) of _ {
False -> : (I# (*# ww1_sYp 2)) ($wgo_sYr (+# ww1_sYp 1));
True -> []
}; } in
$wgo_sYr 0
bloob :: Int -> [Int]
bloob =
\ (w_sYs :: Int) ->
case w_sYs of _ { I# ww1_sYv -> $wbloob ww1_sYv }
unfoldr
正在重写它以参与“折叠/构建”融合,这是 GHC 列表库中使用的优化框架。 “折叠/构建”融合和更新的、不同平衡的“流融合”(在
vector
库中使用)的想法是,如果列表由“好的生产者”生成,则由“好的转换器”转换,并被“好消费者”消费,那么列表 conses 根本不需要分配。老
unfoldr
不是一个好的制作人,所以如果你制作了一个带有
unfoldr
的列表并将其与
foldr
一起使用,随着计算的进行,列表的各个部分将被分配(并立即变成垃圾)。现在,
unfoldr
是一个很好的生产者,所以你可以写一个循环,比如说,
unfoldr
,
filter
, 和
foldr
,而不是(必然)分配任何内存。
bloob
的定义和严厉的
{-# INLINE bloob #-}
(这东西有点脆弱;好的生产者有时需要明确内联才能好),代码
hooby :: Int -> Int
hooby = sum . bloob
$whooby :: Int# -> Int#
$whooby =
\ (ww_s1oP :: Int#) ->
letrec {
$wgo_s1oL :: Int# -> Int# -> Int#
$wgo_s1oL =
\ (ww1_s1oC :: Int#) (ww2_s1oG :: Int#) ->
case tagToEnum# (==# ww1_s1oC ww_s1oP) of _ {
False -> $wgo_s1oL (+# ww1_s1oC 1) (+# ww2_s1oG (*# ww1_s1oC 2));
True -> ww2_s1oG
}; } in
$wgo_s1oL 0 0
hooby :: Int -> Int
hooby =
\ (w_s1oM :: Int) ->
case w_s1oM of _ { I# ww1_s1oP ->
case $whooby ww1_s1oP of ww2_s1oT { __DEFAULT -> I# ww2_s1oT }
}
Maybe
s,没有对;它执行的唯一分配是
Int
用于存储最终结果(
I#
到
ww2_s1oT
的应用)。可以合理地预期整个计算将在机器寄存器中执行。
zipWith
zipWith
有一个奇怪的故事。它有点笨拙地适合折叠/构建框架(我相信它在流融合方面工作得更好)。可以制作
zipWith
fuse 与它的第一个或第二个列表参数,并且多年来,列表库试图使其与其中任何一个融合,如果其中一个是一个好的生产者。不幸的是,使其与第二个列表参数融合可能会使程序在某些情况下的定义更少。即,使用
zipWith
的程序在没有优化的情况下编译时可以正常工作,但在使用优化编译时会产生错误。这不是一个很好的情况。因此,截至
base-4.8
,
zipWith
不再尝试与它的第二个列表参数融合。如果你想让它与一个好的生产者融合,那个好的生产者最好在第一个列表参数中。
zipWith
的引用实现导致期望,例如,
zipWith (+) [1,2,3] (1 : 2 : 3 : undefined)
会给
[2,4,6]
,因为它一到达第一个列表的末尾就停止了。与之前的
zipWith
实现,如果第二个列表看起来像这样,但由一个好的生产者制作,并且如果
zipWith
碰巧与它融合而不是第一个列表,然后它就会繁荣起来。
关于performance - 展开器与 zipWith 的效率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32521479/
我正在实现一个函数 combine::[[a]] -> [[b]] -> (a -> b -> c) -> [[c]] 它给出两个 2D 列表,将给定函数 f::a -> b -> c 应用于 2D
我想总结一个压缩列表。 averageGrade :: [Float] -> [Int] -> Float averageGrade [0.75 , 0.25] [6, 4] , result: 0,
我正在尝试实现经典的高阶范围 zipWith如下 import std.traits: allSatisfy; import std.range: isInputRange; auto zipWith
我正在尝试编写一个具有类型安全长度的向量库,这意味着添加两个不同长度的向量将不会成功。 我目前的实现大致是: data Natural where Zero :: Natural Succ :
Haskell 的 zipWith 的类似物是什么? Python 中的函数? zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] 最佳答案 map() map
初步说明:这是 a deleted question by SeanD 的转版. 就像有 zipWith对于列表... GHCi> zipWith (+) [1,2] [3,4] [4,6] ...感
我的空间泄漏发生在我的一个个人项目中。但我不希望有人在我的项目中解决它。我想了解它。 我通过制作这个算法重现了我的空间泄漏: u 是由以下定义的序列: u(0) = 1 u(1) = 2 u(2) =
在代码审查中,我回答了一个关于 naive Haskell fizzbuzz solution 的问题。通过建议 iterates forward 的实现,避免了增加素数的二次成本和(几乎)完全丢弃模
我已经到了这一步: implicit def collectionExtras[A](xs: Iterable[A]) = new { def zipWith[B, C, That](ys: It
我一直在尝试在不使用惰性 zipwith 的情况下实现从 0 到 n 的斐波那契数列列表方法。到目前为止,我所拥有的是从 n 返回列表的代码。到 1. 有什么办法可以更改此代码,使其从 0- n 返回
我已经使用递归重写了 zipWith 函数,现在我尝试使用列表理解重写它。我遇到了很多绑定(bind)错误,并且我知道我的第二行不正确。这是我的函数,它的工作原理类似于使用递归的 zipWith: z
我必须创建一个名为 differences 的函数,在其中我使用 zipWith 计算每对的差异并将其放入列表中。 例如 差异 [1..5] == [1, 1, 1, 1]。 所以 [2-1, 3-2
我必须创建一个名为 differences 的函数,在其中我使用 zipWith 计算每对的差异并将其放入列表中。 例如 差异 [1..5] == [1, 1, 1, 1]。 所以 [2-1, 3-2
我有两个大小相等的数组,我想按元素组合它们。做这个的最好方式是什么? array 包似乎没有提供 zipWith 等效函数。 我不太愿意做自己的函数,因为我能想到的主要方法是用列表来回转换。我关心速度
处理业务的时候一定有这样的需求:将多个源数据压缩成一个,Reactor提供了zip和zipWith方法可以做到这一点。 zip和zipwith有些不同: zip可以一次合并多个源 zipWiht一次只
我想要一个通用的 zipWith 函数在 C++ 变量arity。我有两个问题。首先是我无法确定传递给 zipWith 的函数指针的类型。它必须与传递给 zipWith 的 vector 数量相同,并
我一直在尝试理解这段代码,但我无法清楚地概括它: ghci > :t zipWith zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] ghci > :t (
我正在尝试在 Haskell 中编写 Zipwith 函数。 如果我使用以下值运行它,它应该返回以下结果: Prelude> zipWith (+) [10,20,30] [33,44,94] [43
ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]] 函数 zipWith' 使用函数 '
我正在使用 Haskell 表达学院学习 Haskell:通过多媒体学习函数式编程,我不确定如何解决这个练习。 Using the definition of trees given by data
我是一名优秀的程序员,十分优秀!