小编Mai*_*tor的帖子

我无法理解Y-combinator,所以我尝试实现一个在没有本机实现的情况下启用递归的函数.经过一番思考,我最终得到了这个:

Y = ?x.(?v.(x x) v)

哪个比实际的短:

Y = ?f.(?x.f (x x)) (?x.f (x x))

而且,令我惊讶的是,工作.一些例子:

// JavaScript
Y = function(x){
  return function(v){
    return x(x, v);
  };
};
sum = Y(function(f, n){
  return n == 0 ? 0 : n + f(f, n - 1);
});
sum(4);

; Scheme
(define Y (lambda (x) (lambda (v) (x x v))))
(define sum (Y 
    (lambda (f n) 
        (if (equal? n 0) 
            0 
            (+ n (f f (- n 1)))))))
(sum 4)

两个片段按预期输出10(从0到4的总和).

这是什么,为什么它更短,为什么我们更喜欢更长的版本？

例如,给出以下树数据类型:

data Tree a = Node [Tree a] | Leaf a deriving Show
type Sexp = Tree String

如何使用高阶组合器表达"漂亮"功能,该组合打印出适当缩进的树？例如:

sexp = 
    Node [
        Leaf "aaa", 
        Leaf "bbb",
        Node [
            Leaf "ccc",
            Leaf "ddd",
            Node [
                Leaf "eee",
                Leaf "fff"],
            Leaf "ggg",
            Leaf "hhh"],
        Leaf "jjj",
        Leaf "kkk"]
pretty = ????
main = print $ pretty sexp

我希望该程序的结果是:

(aaa 
   bbb 
   (ccc 
       ddd 
       (eee 
           fff) 
       ggg 
       hhh) 
   jjj 
   kkk) 

这是一个不完整的解决方案,使用"fold"作为组合器,不实现缩进:

fold f g (Node children) = f (map (fold f g) children) …

在Haskell中,我创建了一个1000000 IntMaps的Vector.然后我使用Gloss以一种访问该向量的随机位图的方式呈现图片.
也就是说,我把每一个都留在了记忆中.渲染函数本身非常轻量级,因此性能应该很好.
然而,该计划以4fps的速度运行.在分析时,我注意到95%的时间花在了GC上.足够公平:
GC疯狂地扫描我的矢量,即使它永远不会改变.

有没有办法告诉GHC "这个大的价值是必要的,不会改变 - 不要试图在其中收集任何东西".

编辑:下面的程序足以复制问题.

import qualified Data.IntMap as Map
import qualified Data.Vector as Vec
import Graphics.Gloss
import Graphics.Gloss.Interface.IO.Animate
import System.Random

main = do
    let size  = 10000000
    let gen i = Map.fromList $ zip [mod i 10..0] [0..mod i 10]
    let vec   = Vec.fromList $ map gen [0..size]
    let draw t = do 
            rnd <- randomIO :: IO Int
            let empty = Map.null $ vec Vec.! mod rnd size
            let rad   = if …

我正在为交互网编译lambda演算术语,以便使用Lamping的抽象算法来评估它们.为了测试我的实现,我使用了这个教堂号码除法功能:

div = (? a b c d . (b (? e . (e d)) (a (b (? e f g . (e (? h . (f h g)))) (? e . e) (? e f . (f (c e)))) (b (? e f . e) (? e . e) (? e . e)))))

除以4(即(? k . (div k k)) (? f x . (f (f (f (f x)))))),我得到这个网:

(抱歉可怕的渲染.?是一个lambda,R是root,D是粉丝,e是橡皮擦.) …

记住这个计划:

{-# LANGUAGE RankNTypes #-}

import Prelude hiding (sum)

type List h = forall t . (h -> t -> t) -> t -> t

sum_ :: (Num a) => List a -> a
sum_ = \ list -> list (+) 0

toList :: [a] -> List a
toList = \ list cons nil -> foldr cons nil list

sum :: (Num a) => [a] -> a
-- sum = sum_ . toList        -- does not work
sum = \ …

我正在使用一种相当丑陋的方法:

var app = require('express')(),
    server = require('http').createServer(app),
    fs = require('fs');
server.listen(80);

path = "/Users/my/path/";

var served_files = {};
["myfile1.html","myfile2.html","myfile3.html"].forEach(function(file){
    served_files["/"+file] = fs.readFileSync(path+file,"utf8");
});

app.use(function(req,res){
    if (served_files[req.path]) 
        res.send(files[req.path]);
});

这样做的正确方法是什么？

在尝试了几个实现深度比较和复制JSON可序列化对象之后,我注意到最快的只是:

function deep_clone(a){
   return JSON.parse(JSON.stringify(a));
};
function is_equal(a,b){
    return JSON.stringify(a) === JSON.stringify(b);
};

不过,我觉得这是作弊.就像我会发现一些会在将来惹恼我的问题.使用它们可以吗？

来自wiki.haskell.org:

首先,公共子表达式消除(CSE)意味着如果表达式出现在多个位置,则重新排列代码,以便仅计算该表达式的值一次.例如:

foo x = (bar x) * (bar x)

Run Code Online (Sandbox Code Playgroud)

可能会变成

foo x = let x' = bar x in x' * x'

Run Code Online (Sandbox Code Playgroud)

因此,bar函数只被调用一次.(如果bar是一个特别昂贵的功能,这可能会节省很多工作.)GHC实际上并不像你期望的那样经常执行CSE.问题是,执行CSE会影响程序的严格性/懒惰性.所以GHC确实做了CSE,但仅在特定情况下---参见GHC手册.(部分？？)

长话短说:"如果你关心CSE,那就亲手做吧."

我想知道在什么情况下CSE"影响"程序的严格/懒惰以及可能产生什么样的影响.

假设我们有一个简单的语法规范.有一种方法可以枚举该语法的术语,通过对角迭代来保证任何有限项都具有有限的位置.例如,对于以下语法:

S      ::= add
add    ::= mul | add + mul
mul    ::= term | mul * term
term   ::= number | ( S )
number ::= digit | digit number
digit  ::= 0 | 1 | ... | 9

您可以枚举这样的术语:

0
1
0+0
0*0
0+1
(0)
1+0
0*1
0+0*0
00
... etc

我的问题是:有没有办法做相反的事情？也就是说,采用该语法的有效术语,比如说0+0*0,并在这样的枚举中找到它的位置 - 在这种情况下,9？

是否有更快的替代以下表达式:

Math.pow(2,Math.floor(Math.log(x)/Math.log(2)))

也就是说,取最接近(较小)的2的整数倍？我在内循环中有这样的表达.我怀疑它可能会快得多,考虑到可以从双尾的IEEE 754表示中获取尾数.