小编vis*_*vis的帖子

我一直在玩Haskell中的RB树实现但是很难改变它,所以数据只放在叶子中,就像在二叉叶树中一样:

    /+\
   /   \
 /+\    \
/   \    c
a   b

除了节点的颜色之外,内部节点还将保存其他信息,例如树的大小(如在普通RB树中,但数据保存在叶子中).我也不需要对要插入的数据进行排序.我只使用RB来获取平衡树,因为我插入数据但我想保持插入数据的顺序.

原始代码是(来自冈崎书):

data Color = R | B
data Tree a = E | T Color (Tree a ) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x s = makeBlack (ins s)
    where ins E = T R E x E
        ins (T color a y b) 
            | x < y = balance color (ins a) y b
            | x …

我想编写一个策略来并行计算数组中的项.旧策略必须parArr这样做(见这里).但是在新的Control.Parallel.Strategies模块中找不到这个.

例如并行列表评估: map f myList `using` parList rdeepseq

我希望能够执行以下操作:amap f myArr `using` parArr rdeepseq,amap来自Data.Array.Base,并将函数应用于每个元素(顺序).

以下似乎工作,但我想知道它是否正确,并想知道我如何定义自己的parArr.

这有效: amap ((+1) `using` rpar) $ Array.array (0,4) [(0,10),(1,20),(2,30),(3,40),(4,50)]

我有一个巨大的haskell文件,编译和运行没有任何问题.我想将一些函数和类型定义放在一个通用hs文件中的单独模块中,然后将其导入到我的主模块中.虽然主程序编译没有任何错误(它也编译导入的模块),但当我尝试运行它时,我得到一个堆栈空间溢出.

我试过了:

ghc --make -O2 Main.hs
./Main -- stack space overflow

也:

ghc --make -O2 Main.hs Other.hs -o RunMe
./RunMe -- again, stack space overflow

这是编译的正确方法还是我遗漏了什么？

假设一台机器有8个核心.在Haskell中,您可以使用该threaded选项进行编译,然后在运行时使用期间+RTS -Nx指定要使用的核心数.例如

$ myprg args // sequential run
$ myprg args +RTS -N1 // parallel run on 1..8 cores
$ myprg args +RTS -N2
$ myprg args +RTS -N4
$ myprg args +RTS -N8

通过这种方式,您可以使用越来越多的内核获得运行时,然后您可以使用这些内核来获得加速并绘制图形.

如果我有一个并行程序,例如在代码中使用并行映射,你将如何在F#中执行此操作？

编辑: 我发现有ParallelOptions,例如MaxDegreeOfParallelism,这可能是我需要但不确定它的确切行为,我必须以编程方式使用它,只要它的行为符合预期,即MaxDegreeOfParallelism=核心程序应使用的数量,并且不是并行的'任务'或线程.

编辑: ProcessorAffinity确实限制了使用的核心数量,但似乎它没有在Mono中正确实现.我检查了Windows,它似乎工作.虽然使用它并不是一个好主意.运行时系统应该能够更好地决定如何管理和安排任务.此外,MaxDegreeOfParallelism关于"并行度"基本上设置了生成的任务数,因此可用于改变粒度.

我正在将一些Haskell代码移植到F#,但对F#中可用的集合及其签名有点困惑.我的理解是列表中的元素包含在[]之间,{}之间的序列和[|之间的数组]之间 |].在F#Interactive中,当我用5个int创建每个容器时,我得到以下内容.

// List
> [1..5]
val it : int list = [1; 2; 3; 4; 5]

// Seq
> {1..5}
val it : seq<int> = seq [1; 2; 3; 4; ...]

// Array
> [|1..5|]
val it : int [] = [|1; 2; 3; 4; 5|]

令我困惑的是数组的类型签名是int [].可能是打字int array还是int [||]不那么混乱？查看类型签名,我倾向于认为它是一个列表,特别是因为空列表也表示为[].

这里有一个问题:为什么序列类型seq<int>而不是int seq.我假设这可能是语法糖,但可能还有其他背后的东西.

现在使用集合创建新类型:

type T1 = T1 of int list
type T2 = T2 of int seq // becomes …

是否有更好,更简洁的方法在Haskell中编写以下代码？我已经尝试过使用if..else但是可读性低于以下内容.我想避免遍历xs列表(这是巨大的!)8次,只是将元素分成8组.groupByfrom Data.List只需要一个测试条件函数:(a -> a -> Bool) -> [a] -> [[a]].

x1 = filter (check condition1) xs
x2 = filter (check condition2) xs
x3 = filter (check condition3) xs
x4 = filter (check condition4) xs
x5 = filter (check condition5) xs
x6 = filter (check condition6) xs
x7 = filter (check condition7) xs
x8 = filter (check condition8) xs
results = [x1,x2,x3,x4,x5,x6,x7,x8]

在Haskell中定义无限列表:

[1,1..] => [1,1,1,..]

或者,循环方式:

lst=1:lst

第一个定义与第二个相同吗？如果没有,哪一个是首选方式？

我怎么能在"不太严格"的表达式中使左手总和,以便我不评估整个列表xs.在该示例中,只有前3个元素足以知道第二个表达式(True)的结果.

xs=[1..10]
sum xs > 3

ghci的:

?> let xs = [1..10]
?> :sp xs
xs = _
?> sum xs > 3
True
?> :sp xs
xs = [1,2,3,4,5,6,7,8,9,10] 

我有两个版本的相同程序,两者之间的变化很小.我没有使用单独的文件,而是使用#if defined (PAR)- #else- #endif然后在有或没有-cpp -DPAR在两个版本之间切换的情况下进行编译.我喜欢这种方式,因为你只需要处理一个单独的hs文件.但是,由于我的目标是编写原始程序的并行/优化版本,我想知道使用#if-#else#-endif是否有任何性能影响？基本上我想解释一下这是如何工作的.谢谢

#if defined(PAR)
import Control.Parallel
import Control.Parallel.Strategies
import Control.DeepSeq
#endif

#if defined(PAR)
test = sum ( map expensiveFunc myList `using` strat )
    where strat = parListChunk 100 rseq
#else 
test = sum ( map expensiveFunc myList )
#endif

注意:

-cpp您可以使用源文件中的语言选项而不是标志:

例如 {-# LANGUAGE CPP #-}

但是-Dxxx在编译时仍需要提供(或不提供),以便选择编译器应该忽略的程序部分(其中xxx是hs文件中定义的变量).

只是好奇.如果我有2个线程产生使用forkIO,它们之间的通信可以使用MVar.我想知道在使用并行Haskell的spark时是否同样适用par.我理解par不会创建一个实际的线程,而只是指向可以并行发生的某些计算的指针.

以下代码编译,main引发以下错误:thread blocked indefinitely in an MVar operation.

t1 a = putMVar a "Hi"
t2 a = do
  v <- takeMVar a
  print v

main1 = do
  a <- newEmptyMVar
  forkIO (t1 a)
  forkIO (t2 a)

main = do
  a <- newEmptyMVar
  (t1 a) `par` (t2 a)   

关于尾递归函数有几个问题,例如这个和这个但是找不到类似于下面的东西.

我的理解是尾部调用优化函数应该在其最后一次调用中返回累积值而无需进一步评估.使用因子函数很容易理解,例如,它被优化为循环2.但在其他情况下,例如在下面,最后一次电话是什么,并不总是显而易见的？它们中有很多因为函数在体内不止一次被称为递归.

Brian提出了一种查找方法,但我不确定如何使尾调用优化.我可以将--tailcalls标志传递给编译器自动执行但是它总是成功吗？

f并g返回相同的类型.

type T = T of int * T list

let rec myfunc f (T (x,xs)) =
    if (List.isEmpty xs) then f x
    else 
        List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

任何有关尾部调用优化上述代码的帮助都将非常感激.

我发现很难在数据类型定义中获得关于编码函数的直觉.这是在State和IO类型的定义中完成的,例如

data State s a = State s -> (a,s)
type IO a = RealWorld -> (a, RealWorld) -- this is type synonym though, not new type

我想看一个更简单的例子来理解它的价值,所以我可以在此基础上建立更复杂的例子.例如,假设我有一个数据结构,那么在一个数据构造函数中编码函数是否有意义.

data Tree = Node Int (Tree) (Tree) (? -> ?) | E

我不确定我在这里尝试做什么,但是我可以在这种类型中编码的函数示例是什么？为什么我必须在类型中对其进行编码,但不要将其用作普通函数,我不知道,可能在需要时作为参数传递？