小编mer*_*ict的帖子

我的一个朋友上周提出了一个看似无害的Scala语言问题,我没有得到一个好的答案:是否有一种简单的方法来声明属于某些常见类型类的东西的集合.当然,Scala中没有关于"类型类"的一流概念,因此我们必须从特征和上下文界限(即暗示)来考虑这一点.

具体地说,给定一些T[_]表示类型类型和类型的特征A,B并且C在范围内具有相应的含义T[A],T[B]并且T[C],我们希望声明类似于a的东西List[T[a] forAll { type a }],我们可以在其中抛出实例A,B并且C不受惩罚.这当然在Scala中不存在; 去年的一个问题更深入地讨论了这个问题.

自然的后续问题是"Haskell如何做到这一点？" 那么,GHC尤其具有称为impredicative polymorphism的类型系统扩展,在"Boxy Types"论文中有所描述.简而言之,给定一个类型类,T可以合法地构建一个列表[forall a. T a => a].给定这种形式的声明,编译器会执行一些字典传递魔术,它允许我们在运行时保留与列表中每个值的类型相对应的类型类实例.

事实是,"字典传递魔法"听起来很像"vtables".在像Scala这样的面向对象语言中,子类型是一种比"Boxy类型"方法更简单,更自然的机制.如果我们的A,B以及C所有延伸的特性T,那么我们可以简单地宣布List[T]并且快乐.同样,作为万里注意到,在评论下面,如果他们都继承特质T1,T2并且T3然后我可以使用List[T1 with T2 with T3]作为等同于impredicative哈斯克尔[forall a. (T1 …

在阅读哈斯克尔有关的东西,我有时会遇到表达"绑结",我想我明白了什么是这样,而不是如何.

那么,对这个概念有什么好的,基本的,简单易懂的解释吗？

我正在努力在Haskell中实现UCT算法,这需要大量的数据杂耍.没有太多细节,它是一个模拟算法,在每个"步骤",基于一些统计属性选择搜索树中的叶节点,在该叶子上构造新的子节点,并且对应于新叶及其所有祖先都会更新.

鉴于所有这些杂耍,我并不是非常敏锐,无法弄清楚如何使整个搜索树成为Okasaki的一个不可改变的数据结构.相反,我一直在玩STmonad,创建由可变STRefs 组成的结构.一个人为的例子(与UCT无关):

import Control.Monad
import Control.Monad.ST
import Data.STRef

data STRefPair s a b = STRefPair { left :: STRef s a, right :: STRef s b }

mkStRefPair :: a -> b -> ST s (STRefPair s a b)
mkStRefPair a b = do
    a' <- newSTRef a
    b' <- newSTRef b
    return $ STRefPair a' b'

derp :: (Num a, Num b) => STRefPair s a b -> ST s …

鉴于:

Applicative m, Monad m => mf :: m (a -> b), ma :: m a

它似乎被认为是一项法律:

mf <*> ma === do { f <- mf; a <- ma; return (f a) }

或者更简洁:

(<*>) === ap

说的文档Control.Applicative<*>是"顺序应用程序",这表明了这一点(<*>) = ap.这意味着<*>必须从左到右依次评估效果,以保持一致>>=...但这感觉不对.McBride和Paterson的原始论文似乎暗示从左到右的排序是任意的:

IO monad,实际上任何Monad,都可以通过取pure= return和<*>=来实现ap.我们也可以使用它的变量ap以相反的顺序执行计算,但我们将在本文中保持从左到右的顺序.

因此,有两个合法的,非平凡的推导<*>来源于>>=并且return具有不同的行为.在某些情况下,既没有这两个推导是可取的.

例如,(<*>) === …

我正在研究一个涉及绑定大结的Haskell项目:我正在解析图的序列化表示,其中每个节点都在文件的某个偏移处,并且可以通过其偏移引用另一个节点.所以我需要在解析时建立从偏移到节点的映射,我可以在一个do rec块中反馈给自己.

我有这个工作,有点合理地抽象成一个StateT-esque monad变换器:

{-# LANGUAGE DoRec, GeneralizedNewtypeDeriving #-}

import qualified Control.Monad.State as S

data Knot s = Knot { past :: s, future :: s }

newtype RecStateT s m a = RecStateT (S.StateT (Knot s) m a) deriving
  ( Alternative
  , Applicative
  , Functor
  , Monad
  , MonadCont
  , MonadError e
  , MonadFix
  , MonadIO
  , MonadPlus
  , MonadReader r
  , MonadTrans
  , MonadWriter w )

runRecStateT :: RecStateT s m a -> Knot …

好的,公平的警告:这是我上周的荒谬问题的后续行动.虽然我认为这个问题并不荒谬.无论如何,这里是:

以前荒谬的问题:

假设我有一些T带有子类的基本特征A,B并且C,我可以声明一个集合Seq[T],例如,可以包含类型的值A,B和C.让子类型更明确,让我们使用Seq[_ <: T]类型绑定语法.

现在假设我有一个TC[_]带有成员的类型类A,B并且C(其中"成员"表示编译器可以TC[A]在隐式作用域中找到一些等等).与上面类似,我想Seq[_ : TC]使用上下文绑定语法声明一个类型的集合.

这不是合法的Scala,并且试图模仿可能会让你觉得自己是一个坏人.请记住,上下文绑定语法(正确使用时!)desugars到正在定义的类或方法的隐式参数列表,这在这里没有任何意义.

新前提:

因此,我们假设类型类实例(即隐式值)是不可能的,而在这种情况下我们需要使用隐式转换.我有一些类型V("v"应该代表"view",fwiw),以及范围内的隐式转换A => V,B => V以及C => V.现在我可以填充一个Seq[V],尽管如此A,B并且C不相关.

但是,如果我想要什么东西都是隐式转换既视图的集合V1和V2？我不能说Seq[V1 with V2]因为我的隐含转换并没有神奇地聚合这种方式.

隐式转换的交集？

我这样解决了我的问题:

// a …

在Haskell中,liftM2可以定义为:

liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2 = do
  x1 <- m1
  x2 <- m2
  return $ f x1 x2

我想把它翻译成Scala.我的第一次尝试如下:

def liftM2[T1, T2, R, M[_]](f: (T1, T2) => R)(ma: M[T1], mb: M[T2]) : M[R] = for {
  a <- ma
  b <- mb
} yield f(a, b)

我认为这是最明显的可行方式:"flat flatMap不是类型参数M [T1]的成员".是的,我没有说明M[_]是某种单子.所以接下来我尝试的是定义一些结构类型,如:

type Monad[A] = {
  def flatMap[B](f: (A) => …

GHC有几个语言标志,如DeriveFunctor,DeriveDataTypeable等,使能比那些允许在Haskell 98本其他类型的类派生的实例编译生成特别有意义的东西一样Functor,在这个类的法律规定明显,"自然的"衍生实例".

那么为什么不Monoid呢？对于具有单个数据构造函数的任何数据类型,似乎:

data T = MkT a b c ...

一个人可以机械地产生一个Monoid实例(原谅伪代码):

instance (Monoid a, Monoid b, Monoid c, ...) => Monoid T where
  mempty =
    MkT mempty mempty mempty ...
  mappend (MkT a1 b1 c1 ...) (MkT a2 b2 c2 ...) =
    MkT (mappend a1 a2) (mappend b1 b2) (mappend c1 c2) ...

我知道派生包提供了这个,但我的问题具体是GHC没有的原因.

我正在Haskell写一个brainfuck解释器,我想出了一个我认为对程序非常有趣的描述:

data Program m = Instruction (m ()) (Program m)
               | Control (m (Program m))
               | Halt

但是,将brainfuck程序的文本表示解析为此数据类型是很棘手的.尝试正确解析方括号时会出现问题,因为有一些结点可以使Instruction循环中的最终内容Control再次链接到循环.

更多初步信息.有关所有详细信息,请参阅github repo上的此版本.

type TapeM = StateT Tape IO
type TapeP = Program TapeM
type TapeC = Cont TapeP

branch :: Monad m => m Bool -> Program m -> Program m -> Program m
branch cond trueBranch falseBranch =
  Control ((\b -> if b then trueBranch else falseBranch) `liftM` cond)

loopControl :: TapeP -> TapeP -> …

在以下简化的示例代码中:

case class One[A](a: A) // An identity functor
case class Twice[F[_], A](a: F[A], b: F[A]) // A functor transformer
type Twice1[F[_]] = ({type L[?] = Twice[F, ?]}) // We'll use Twice1[F]#L when we'd like to write Twice[F]

trait Applicative[F[_]] // Members omitted
val applicativeOne: Applicative[One] = null // Implementation omitted
def applicativeTwice[F[_]](implicit inner: Applicative[F]): Applicative[({type L[?] = Twice[F, ?]})#L] = null

我可以在applicativeOne上调用applicativeTwice,并且类型推断工作,一旦我尝试在applicativeTwice(applicativeOne)上调用它,推理就会失败:

val aOK = applicativeTwice(applicativeOne)
val bOK = applicativeTwice[Twice1[One]#L](applicativeTwice(applicativeOne))
val cFAILS = applicativeTwice(applicativeTwice(applicativeOne))

scala 2.10.0中的错误是

- type mismatch; …