小编mcm*_*yer的帖子

假设您有一个序列化器/反序列化器类型类

class SerDes a where
    ser :: a -> ByteString
    des :: ByteString -> a

事实证明，对于每种类型都有一个特殊的辅助函数是至关重要的a，例如

compress :: ByteString -> ByteString     -- actually varies with the original type

我认为compress作为一个功能，我想每个关联a这是一个SerDes。（“associate”这个词可能是一个糟糕的选择，这也是互联网搜索一无所获的原因。）

该示例并不像看起来那样做作，例如何时decompress是串行器/解串器的可选功能。（是的，可以通过增加ser控制压缩的开关来避免使用助手 ser:: a -> Bool -> ByteString，或者更好地使用Config记录。但让我们坚持这个例子。）

一种方法是一个“虚拟”类，一个单例：

data For a = For

然后这将起作用：

class SerDes a where
    ser      :: a -> ByteString
    des      :: ByteString -> a
    compress :: For a -> ByteString -> ByteString …

在不断努力有效地摆弄比特的过程中(例如,参见这个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 …

最直接的monadic'stream'只是一系列monadic动作Monad m => [m a].该sequence :: [m a] -> m [a]函数评估每个monadic动作并收集结果.事实证明,sequence并不是非常有效,因为它在列表上运行,并且monad是在除了最简单的情况之外的任何事情中实现融合的障碍.

问题是:对于monadic流来说,最有效的方法是什么？

为了解决这个问题,我提出了一个玩具问题以及一些提高性能的尝试.源代码可以在github上找到.下面提出的单一基准可能会误导更现实的问题,尽管我认为这是最糟糕的情况,即每次有用计算的最大开销.

玩具问题

是一个最大长度的16位大号 inear ˚F eedback 小号 HIFT ř egister(LFSR),在C以稍微过精心方式实施,在一个Haskell包装IO单子."过度复杂的"是指不必要使用的struct和它malloc-这种并发症的目的是使其更类似于所有你必须是围绕一个FFI Haskell的包装到一个C现实情况struct与OO十岁上下new,set,get,operate语义(即非常多的命令式).典型的Haskell程序如下所示:

import LFSR

main = do
    lfsr <- newLFSR            -- make a LFSR object
    setLFSR lfsr 42            -- initialise it with 42 
    stepLFSR lfsr              -- do one update
    getLFSR lfsr >>= print …

类型化的无标签最终解释器是免费的monad方法的一种有趣替代方法。

但是，即使使用无ToyLang标签的最终样式中的一个非常简单的示例，仍然会弹出模糊的类型变量。

ToyLang 是一个EDSL，应读取以下内容：

toy :: ToyLang m => m (Maybe Int)
toy = do
    a <- int "a"       -- declare a variable and return a reference
    a .= num 1         -- set a to 1
    a .= a .+ num 1    -- add 1 to a
    ret a              -- returns a

当然，总的目标是在此EDSL中尽可能多地使用Haskell类型系统，并使用多态来实例化各种解释器。

如果不是用于(.+)导致左值和右值概念的运算，那么一切都会很好：赋值运算符(.=)的左侧是左值，而右侧是左值或右值。基本思想来自于“ 强制多态性”中的两个注释，一个用例：

{-# LANGUAGE GADTs #-}

data L -- dummies for Expr (see the comments …

为了确定我是否可以/应该使用 Rust 而不是默认的 C/C++，我正在研究各种边缘情况，主要考虑到这个问题：在 0.1% 的情况下，它确实很重要，我总能得到编译器输出与 gcc 一样好（具有适当的优化标志）？答案很可能是否定的，但让我们看看......

Reddit上有一个相当特殊的示例，研究无分支排序算法的子例程的编译器输出。

这是基准 C 代码：

#include <stdint.h>
#include <stdlib.h>
int32_t* foo(int32_t* elements, int32_t* buffer, int32_t pivot)
{
    size_t buffer_index = 0;

    for (size_t i = 0; i < 64; ++i) {
        buffer[buffer_index] = (int32_t)i;
        buffer_index += (size_t)(elements[i] < pivot);
    }
}

这是带有编译器输出的godbolt 链接。

Rust 的第一次尝试如下所示：

pub fn foo0(elements: &Vec<i32>, mut buffer: [i32; 64], pivot: i32) -> () {
    let mut buffer_index: usize = 0;
    for i in 0..buffer.len() {
        buffer[buffer_index] …

该vector-0.1包具有非常高效的Stream实现(Data.Vector.Stream):

data Step s a = Yield a s
              | Skip    s
              | Done

-- | The type of fusible streams
data Stream a = forall s. Stream (s -> Step s a) s Size

后来的版本将其vector扩展为monadic版本Data.Vector.Fusion.Stream.Monadic,但为了简单起见,让我们使用旧的,非monadic版本.

Stream很自然地是Functor和的一个例子Foldable:

instance Foldable Stream where
    foldMap f s = foldl' (\a b -> a <> (f b)) mempty s

作为一个流,它也应该是一个实例Traversable,不应该吗？至少乍一看它看起来很简单.我们需要一个

sequenceA :: Applicative f => Stream (f …

虽然我有一个很好的LSFR C实现,我想我会在Haskell中尝试相同 - 只是为了看看它是怎么回事.到目前为止,我想出的是比C实现慢两个数量级,这引出了一个问题:性能如何得到改善？显而易见,这个小小的操作是瓶颈,而分析器确认了这一点.

这是使用列表的基线Haskell代码,并且Data.Bits:

import           Control.Monad      (when)
import           Data.Bits          (Bits, shift, testBit, xor, (.&.), (.|.))
import           System.Environment (getArgs)
import           System.Exit        (exitFailure, exitSuccess)

tap :: [[Int]]
tap = [
    [],            [],            [],            [3, 2],
    [4, 3],        [5, 3],        [6, 5],        [7, 6],
    [8, 6, 5, 4],  [9, 5],        [10, 7],       [11, 9],
    [12, 6, 4, 1], [13, 4, 3, 1], [14, 5, 3, 1], [15, 14],
    [16,15,13,4],  [17, 14],      [18, 11],      [19, 6, 2, 1],
    [20, …

我有一个基于 cmake 的小型 C++11 库，可以通过使用一些 C++14 和一些 C++17 特性来改进。

为此，我希望 CMake 测试cxx_std_14和/或cxx_std_17是否在列表CMAKE_CXX_COMPILE_FEATURES 中，如相关的 SO 问题How to detect C++11 support of a compiler with CMake 中所暗示的那样。

不过，我不太清楚如何编写此测试。我认为应该起作用的，不起作用：

list (FIND ${CMAKE_CXX_COMPILE_FEATURES} "cxx_std_14" _index)
if (${_index} GREATER -1)
   message("YAY 14")
else()
   message("NAY 14")
endif()

# -> CMake Error .... (list):
#      list sub-command FIND requires three arguments

（因为最小的 CMake 版本是 2.8.7 我必须使用list(FIND ...)而不是更新的、更简洁的IN_LIST）。

CMAKE_CXX_COMPILE_FEATURES 似乎是一个分号分隔的字符串，所以这个丑陋的片段有效：

if ("${CMAKE_CXX_COMPILE_FEATURES}" MATCHES "cxx_std_14") …

我正在尝试构建一个抽象语法树，允许使用 monaddo表示法进行定义，如下所示：

ast = do
    Variable uint8 "i"
    Function Void "f" $ do
        Variable uint8 "local_y"
        Comment "etc. etc."

我在这里展示的结构是从Text.Blaze.Html中收集的，它用于定义 HTML 树。

问题分散在以下各个部分。主要问题是如何正确地做到这一点。当然，任何有助于理解此结构的输入都将受到高度赞赏。

因此，首先，这是一个虽小、有缺陷但“有效”的示例。它是一个语法树，其中包含特定类型的变量和函数的声明、注释行以及用于替换的占位符声明：

{-# LANGUAGE ExistentialQuantification #-}
module Question
where

import           Control.Applicative
import           Data.Monoid         (Monoid, (<>))
import           Data.String.Utils   (rstrip)

type NumberOfBits = Word
type VariableName = String

data Type = UInt NumberOfBits
          | Int NumberOfBits
          | Void

uint8 = UInt 8
int8 = Int 8

instance Show Type where
    show (UInt w) = "uint" <> …

在下面的代码片段中,我最初认为有一个受限制的monad错误(我忘了Monad m =>在instance Monad (Transform m a)定义中添加).读了很多关于受限制的monad后,我想知道为什么这里碰巧是好的:

{-# LANGUAGE GADTs #-}

data Next a where
    Todo :: a -> Next a
    Done :: Next a

instance Functor Next where
    fmap f Done = Done
    fmap f (Todo a) = Todo (f a)

data Transform m a b = Monad m => Transform ( m(Next a) -> m(Next b) )

instance Functor (Transform m a) where
    fmap f (Transform ta) = Transform tb where
        tb ma = …