小编Sri*_*aic的帖子

在过去的几天里,我一直在为第一次软件开发工作的电话采访做准备.在研究问题时,我提出了这篇文章.

在我到达这段经文之前,每件事都很棒

"你什么时候使用链表和矢量？"

现在根据经验和研究,这两个是非常不同的数据结构,链表是动态数组,矢量是空间中的2d点.我可以在两者之间看到的唯一关联是,如果你使用向量作为链表,比方说myVector(my value, pointer to neighbor)

思考？

我写了以下简单的函数

u f=f.f

根据ghci这个有类型签名

u :: (b -> b) -> b -> b

但是这种类型签名太严格了.Haskell强制要求我们的输入是(b -> b)不一定需要的类型.例如,该函数(:[])的类型签名为

(:[]) :: a -> [a]

哪个不是形式(b -> b),(除非你允许无限​​类型)因此不能传递给u.但是你可以(:[])自己组合.

g=(:[]).(:[])

这有效并具有类型

(:[]).(:[]) :: a -> [[a]]

因此,我原则上应该能够将其传递给u.

我试图自己编写一个新的签名来替换生成的签名,但我无法想出一种方法来表达函数的要求.我总是提出编译器提供的相同类型签名.我们可以给出一个类型签名来削弱它,u以便(:[])可以传递给它的函数吗？

为了举例，让我们定义一个玩具自动机类型：

data Automaton =
  Auto
    { success ::
      Automaton
    , failure ::
      Automaton
    }

这个结构被设计成循环的，我们可以把每一个Automaton状态想象成一个成功和失败的状态转换到其他状态。因此有限自动机必须递归定义。例如，这是最简单的自动机：

sink =
  Auto sink sink

它由 1 个总是转换到自身的状态组成。如果我们愿意，我们可以制作更复杂的自动机：

-- Transitions to a sink once it encounters a failure
otto1 =
  Auto otto1 sink

-- Mutually recursive automata
otto2 =
  Auto otto2 otto3

otto3 =
  Auto otto3 otto2

这些都很好。但接受用户输入并构建一个自动机可能会更好。例如，可以从转换矩阵中构建一个。这是一个简单的实现：

fromTransition :: [(Int, Int)] -> Automaton
fromTransition tMatrix =
  go 0
  where
    go n =
      let
        (succ, fail) =
          tMatrix !! n
      in
        Auto (go …

给定一个操作(??)，使得

(a ?? b) ?? c = a ?? (b ?? c)

（也就是说(??)是联想的）

一定是这样

liftA2 (??) (liftA2 (??) a b) c = liftA2 (??) a (liftA2 (??) b c)

（也就是说liftA2 (??)是联想的）

如果我们愿意，我们可以将其重写为：

fmap (??) (fmap (??) a <*> b) <*> c = fmap (??) a <*> (fmap (??) b <*> c)

我花了一点时间盯着适用的法律，但我无法拿出证据证明情况确实如此。所以我开始反驳它。我尝试过的所有开箱即用的应用程序（Maybe、[]、Either等）都遵循法律，所以我想我会创建自己的应用程序。

我最好的想法是制作一个空的应用程序，并附加一条额外的信息。

data Vacuous a = Vac Alg

Alg我稍后会在自己方便的时候定义哪些代数可以使财产失败但适用的法律成功。

现在我们这样定义我们的实例：

instance Functor Vacuous where
  fmap f …

关于串联的一个很好的真实事实是，如果我知道等式中的任何两个变量：

a ++ b = c

然后我知道第三个。

我想在我自己的 concat 中捕捉这个想法，所以我使用了函数依赖。

{-# Language DataKinds, GADTs, FlexibleContexts, FlexibleInstances, FunctionalDependencies, KindSignatures, PolyKinds, TypeOperators, UndecidableInstances #-}
import Data.Kind (Type)

class Concatable
   (m  :: k -> Type)
   (as :: k)
   (bs :: k)
   (cs :: k)
   | as bs -> cs
   , as cs -> bs
   , bs cs -> as
   where
     concat' :: m as -> m bs -> m cs

现在我像这样召唤异类列表：

data HList ( as :: [ Type ] ) where
  HEmpty :: …

最近我注意到，幽默地liftA可以写成

liftA (<*>) pure

我认为这很整洁，所以开个玩笑，我想我将liftA基于此属性做出新的“定义” ：

f = f (<*>) pure

现在，我曾期望这与liftA从未停止过的事情属于同一类型。但是，它无法编译。

• Occurs check: cannot construct the infinite type:
    t ~ (f (a -> b) -> f a -> f b) -> (a1 -> f1 a1) -> t
• In the expression: f (<*>) pure
  In an equation for ‘f’: f = f (<*>) pure
• Relevant bindings include
    f :: (f (a -> b) -> f a -> f b) -> (a1 …

我有一个类型类，看起来有点像以下内容：

class Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

或者至少这些对我的问题很重要。此类没有编译，并且有充分的理由。此类的问题是，我可以（如果愿意）执行以下操作：

instance Foo () Bool where
  f x = True
  g y = y
  h x y = False

instance Foo ((), ()) Bool where
  f x = True
  g y = not y
  h x y = False

现在，如果我打电话g True给每个实例，有两个单独的结果。编译器意识到了这种可能性，并告诉我我的类型类不好。

我的问题是依赖性| a -> b不是我的意思。我不只是意味着你可以找到a从b，还以为你能找到 …

假设出于这个问题的目的，我想为coerce. 我从显而易见的开始

import Data.Coerce

q = coerce

有点令人惊讶的是，这会产生一个错误：

coerce.hs:3:5: error:
    • Couldn't match representation of type ‘a0’ with that of ‘b0’
        arising from a use of ‘coerce’
    • In the expression: coerce
      In an equation for ‘q’: q = coerce
    • Relevant bindings include q :: a0 -> b0 (bound at coerce.hs:4:1)
  |
4 | q = coerce
  |     ^^^^^^

这个错误是相当不透明的，所以我拍了一下类型签名¹的coerce到q：

{-# Language RankNTypes #-}
{-# Language KindSignatures #-}
{-# Language PolyKinds …

直到今天我的假设是fromInteger在Num班是一个环同态。我假设这是因为 integer is 是共同终结符，所以每个环必须有一个来自 integer 的唯一同态，所以它Num基本上是标准库的环类，将包含该同态是有道理的。

不过今天我读了法律Num这一点，锯fromInteger是不是要同态必需的，但只需要保留身份。因此，例如我们可以实现 Klein 4 群，并fromInteger映射1到乘法恒等式和其他一切到加法恒等式，结果是合法Num实例而不是同态。

type Klein4
  = ( Bool
    , Bool
    )

instance
  (
  )
    => Num Klein4
  where
  ( a, b ) + ( c, d )
    = ( a /= c
      , b /= d
      )
  ( a, b ) * ( c, d )
    = ( a && b
      , b && d …

我试图在Haskell中的类型级别实现Integers.首先,我实现了自然数

data Zero
data Succ a

然后我将其扩展为整数

data NegSucc a

我决定然后创建一个Increment增加整数的类.我是这样做的:

{-# Language FunctionalDependencies #-}
{-# Language UndecidableInstances #-}
{-# Language MultiParamTypeClasses #-}
{-# Language FlexibleInstances #-}

import Prelude ()

-- Peano Naturals --

data Zero
data Succ a

class Peano a
instance Peano Zero
instance (Peano a) => Peano (Succ a)

-- Integers --

data NegSucc a -- `NegSucc a` is -(a+1) so that 0 can only be expressed one way

class Integer a
instance (Peano a) …