小编Chr*_*lor的帖子

至少在20世纪90年代末期,人们希望以友好的方式将受限制的monad整合到Haskell中.

例如,在没有限制的单子,你不能进行有效的单子出来Set,Map或者概率分布.这是几年前的一个问题,其中有人碰到了这个问题.

人们提出了各种解决方法,包括:

• 为每个可能的限制创建一个新的类型.

• 使用模板Haskell.

• 使用约束种类.

然而,这些方法似乎都不是"规范的".我在2007年的博客文章中找到了Don Stewart的评论,他在文章中暗示我们与限制使用索引类型的 monad"非常接近" .

现状是什么？现在有一种"规范"的方式来限制单子吗？或者我们仍然生活在变通办法中？

我有一段代码,使用的概率分布重复采样sequence.在道德上,它做了这样的事情:

sampleMean :: MonadRandom m => Int -> m Float -> m Float
sampleMean n dist = do
  xs <- sequence (replicate n dist)
  return (sum xs)

除了它有点复杂.实际的代码我感兴趣的是函数likelihoodWeighting在此Github上回购.

我注意到运行时间非线性地缩放n.特别是,一旦n超过某个值,它就会达到内存限制,并且运行时间会爆炸.我不确定,但我认为这是因为sequence正在构建一长串的thunk,直到调用才会得到评估sum.

一旦我通过大约100,000个样本,该程序就会慢慢爬行.我想优化它(我的感觉是1000万个样本应该不是问题)所以我决定对它进行分析 - 但是我在理解分析器的输出方面遇到了一些麻烦.

剖析

我在一个main.hs运行我的函数的文件中创建了一个简短的可执行文件 这是做的输出

$ ghc -O2 -rtsopts main.hs
$ ./main +RTS -s

我注意到的第一件事 - 它分配了近1.5 GB的堆,并将60%的时间花在垃圾收集上.这通常表明懒惰太多了吗？

 1,377,538,232 bytes allocated in the heap
 1,195,050,032 bytes copied during GC
   169,411,368 bytes maximum residency (12 …

roundHaskell中有关于该函数的官方规范吗？在GHCi版本7.0.3中,我看到以下行为:

ghci> round (0.5 :: Double)
0
ghci> round (1.5 :: Double)
2

由于0.5和1.5都可以完全表示为浮点数,我希望看到与Python中相同的行为:

>>> round(0.5)
1.0
>>> round(1.5)
2.0

是否存在差异的理由,还是GHCi的怪癖？

我正在Haskell中编写一个Lisp(GitHub中的代码)作为一种学习两种语言的方法.

我正在添加的最新功能是宏.不卫生的宏或任何花哨的东西 - 只是普通的香草代码转换.我的初始实现有一个独立的宏环境,与所有其他值所处的环境不同.在read和eval函数之间我散布了另一个函数macroExpand,它在代码树中行走并在宏环境中找到关键字时执行适当的转换,在最终表格传递eval到评估之前.这样做的一个很好的优点是宏具有与其他函数相同的内部表示,这减少了一些代码重复.

虽然有两个环境看起来很笨重,但是如果我想加载一个文件,我eval必须能够访问宏环境以防文件包含宏定义.所以我决定引入宏类型,在与函数和变量相同的环境中存储宏,并将宏扩展阶段合并到eval.我起初有点不知所措,直到我认为我可以写下这段代码:

eval env (List (function : args)) = do
    func <- eval env function
    case func of 
        (Macro {}) -> apply func args >>= eval env
        _          -> mapM (eval env) args >>= apply func

它的工作原理如下:

1. 如果传递一个包含初始表达式和一堆其他表达式的列表......
2. 评估第一个表达式
3. 如果它是一个宏,则将其应用于参数,并评估结果
4. 如果它不是宏,则评估参数并将函数应用于结果

就好像宏与函数完全相同,除了eval/apply的顺序被切换.

这是宏的准确描述吗？通过这种方式实现宏,我错过了一些重要的东西吗？如果答案是"是"和"否",那么为什么我以前从未见过以这种方式解释的宏？

我知道带符号的零用于区分下溢与正数或负数,因此值得区分它们.直觉我觉得-0.0应该是绝对值0.0.但是,这不是Haskell所说的:

Prelude> abs (-0.0)
-0.0

对于它的价值,Python 2.7不同意:

>>> -0.0
-0.0
>>> abs(-0.0)
0.0

这是一个错误,还是标准的一部分？

这是计算斐波纳契数的一个简单函数:

fib :: [Int]
fib = 1 : 1 : zipWith (+) fib (tail fib)

在ghci我可以快速计算系列.事实上,一些实验表明,计算在近似线性的时间内运行.

ghci> last $ take 100000 fib
354224848179261915075         -- takes under a second

如果我将类型签名更改为多态:

fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)

然后算法变慢.事实上,它似乎现在以指数时间运行!

切换到多态类型签名是否意味着列表在每个阶段都被完全重新计算？如果是这样,为什么？

如果输入可以采用无限多的值,则使用列表来模拟非确定性是有问题的.例如

pairs = [ (a,b) | a <- [0..], b <- [0..] ]

这将返回[(0,1),(0,2),(0,3),...]并且永远不会向您显示任何第一个元素不对的对0.

使用Cantor配对功能将列表列表折叠到单个列表中可以解决此问题.例如,我们可以定义一个类似绑定的运算符,它可以更智能地对其输出进行排序

(>>>=) :: [a] -> (a -> [b]) -> [b]
as >>>= f = cantor (map f as)

cantor :: [[a]] -> [a]
cantor xs = go 1 xs
  where
    go _ [] = []
    go n xs = hs ++ go (n+1) ts
      where
        ys = filter (not.null) xs
        hs = take n $ map head ys
        ts = …

在Java中拥有一个具有List的所有功能但具有最大存储容量的数据结构对我来说很有用,并且在添加新数据时丢弃旧数据.可以想象,在某些时候,我可能想要实现一个固定大小的队列,它保持数据的更一般顺序,并在该顺序中丢弃最旧的数据,但这是未来的.

目前我正在实现它:

public class FixedSizeList<T> {

  private final int maxSize;
  private final LinkedList<T> list = new LinkedList<T>();

  public FixedSizeQueue(int maxSize) {
    this.maxSize = maxSize < 0 ? 0 : maxSize;
  }

  public T add(T t) {
    list.add(t);
    return list.size() > maxSize ? list.remove() : null;
  }

  // add remaining methods...

}

是否存在(a)满足我需求的现有数据结构,或者(b)实现此数据结构的更好方法？

我一直在研究计算机程序的结构和解释,并完成Haskell的练习.前两章很好(github上的代码),但第3章让我更难思考.

首先是谈论管理国家,以银行账户为例.他们定义一个函数make-withdraw通过

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

这样您就可以执行以下代码:

(define w1 (make-withdraw 100))
(define w2 (make-withdraw 100))

(w1 50)
50

(w2 70)
30

(w2 40)
"Insufficient funds"

(w1 40)
10

我不确定如何在Haskell中模仿这个.我首先想到了一个使用State monad的简单函数:

import Control.Monad.State

type Cash    = Float
type Account = State Cash

withdraw :: Cash -> Account (Either String Cash)
withdraw amount = state makewithdrawal where
    makewithdrawal balance = if balance …

在Scheme中,原语eq?测试其参数是否是同一个对象.例如,在以下列表中

(define lst
  (let (x (list 'a 'b))
    (cons x x)))

的结果

(eq? (car x) (cdr x))

是真实的,而且它是真实的,而不具有窥视(car x)和(cdr x).这允许您为具有大量共享的数据结构编写有效的相等性测试.

在Haskell中是否可以做同样的事情？例如,请考虑以下二叉树实现

data Tree a = Tip | Bin a (Tree a) (Tree a)

left  (Bin _ l _) = l
right (Bin _ _ r) = r

mkTree n :: Int -> Tree Int
mkTree 0 = Tip
mkTree n = let t = mkTree (n-1) in Bin n t t

在每个级别都有共享.如果我创建一棵树 …