相关疑难解决方法(0)

我目前正在通过在线学习你的Haskell书籍的方式,并且已经到了一个章节,作者正在解释一些列表连接可能效率低下:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f

据说效率低下.作者提出的解决方案是使用定义为的"差异列表"

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

我很难理解为什么DiffList在某些情况下比简单串联更具计算效率.有人可以用简单的语言向我解释为什么上面的例子是如此低效,以及DiffList以什么方式解决了这个问题？

在不断努力有效地摆弄比特的过程中(例如,参见这个SO问题),最新的挑战是比特的有效流和消费.

作为第一个简单的任务,我选择在生成的比特流中找到最长的相同比特序列/dev/urandom.典型的咒语是head -c 1000000 </dev/urandom | my-exe.实际目标是流式比特并解码Elias伽马码,例如,不是字节块或其倍数的码.

对于可变长度的这样的代码它是好的,具有take,takeWhile,group,对于列表操作等语言.由于a BitStream.take实际上会消耗部分b声,因此一些monad可能会发挥作用.

明显的起点是来自的懒惰字节串Data.ByteString.Lazy.

A.计算字节数

正如预期的那样,这个非常简单的Haskell程序与C程序相同.

import qualified Data.ByteString.Lazy as BSL

main :: IO ()
main = do
    bs <- BSL.getContents
    print $ BSL.length bs

B.添加字节

一旦我开始使用unpack东西应该变得更糟.

main = do
    bs <- BSL.getContents
    print $ sum $ BSL.unpack bs

令人惊讶的是,Haskell和C表现出几乎相同的表现.

C.相同位的最长序列

作为第一个非常重要的任务,可以找到最长的相同位序列,如下所示:

module Main where

import           Data.Bits            (shiftR, (.&.))
import qualified Data.ByteString.Lazy as BSL
import …

我想在Haskell中的多态lambda演算中实现该对的Church编码.

在Peter Selinger关于lambda演算的注释的第77页第8.3.3节中,他给出了两种类型的笛卡尔积的构造.

A×B =∀α.(A→B→α)→
α⟨M,N⟩=Λα.λfA ^→B→ α.fMN

对于另一个来源,在第54页,DiderRémy关于lambda演算的注释的第4.2.3节,他将多态λ演算/系统F中的对的教会编码定义为

Λα₁.Λα₂.λx₁:α₁.λx₂:α₂.Λβ.λy:α₁→α₂→β.y x 1 x 2

我认为雷米和塞林格一样,更加啰嗦.

无论如何,根据维基百科,Haskell的类型系统基于System F,所以我希望可以直接在Haskell中实现这个Church编码.我有:

pair :: a->b->(a->b->c)->c
pair x y f = f x y

但我不知道如何进行预测.

Λα.Λβ.λp ^α×β .pα(λx ^α .λy ^β .X)

我是否将Haskell forall用作首都lambda类型量词？

这与我之前的问题基本相同,但在Haskell而不是Swift中.我认为额外的环境和场地的变化可能会让它变得更加明智.

我有这个代码:

import Data.List

newList_bad  lst = foldl' (\acc x -> acc ++ [x*2]) [] lst
newList_good lst = foldl' (\acc x -> x*2 : acc) [] lst

这些函数返回列表,每个元素乘以2:

*Main> newList_bad [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> newList_good [1..10]
[20,18,16,14,12,10,8,6,4,2]

在ghci:

*Main> sum $ newList_bad [1..15000]
225015000
(5.24 secs, 4767099960 bytes)
*Main> sum $ newList_good [1..15000]
225015000
(0.03 secs, 3190716 bytes)

为什么newList_bad功能比它慢200倍newList_good？我知道这不是一个很好的解决方案.但为什么这个无辜的代码工作得如此之慢？

这是什么"4767099960字节"?? 对于那个简单的操作,Haskell使用4 GiB ??

编译后:

C:\1>ghc -O --make test.hs
C:\1>test.exe
225015000
Time for sum (newList_bad [1..15000]) is 4.445889s …