duangsuse::Echo

#algorithm #cs #net #security 🌚 这... 他们也真是太有创意了，这都能想出来（其实也不意外，像这种增加服务资源消耗的破坏性攻击也是直觉所在了...） 🤔 HashMap 的最差时间复杂度，假设是扎堆的情况下可能是 O(n**2) ？看来还是我不了解这些算法.... 我一直以为最差大不了就是 O(n) 的，线性 Map 也就是这个复杂度： #Haskell 里，（List）Map 可以这么定义： data ListMap k a = ListMap [(k, a)]…

data Maybe a = Just a | Nothing deriving Eq, Show

instance Functor Maybe where
  fmap f (Just x) = Just <$> f x
  fmap f Nothing = Nothing

instance Monad Maybe where
  return x = Maybe x
  (Just x) >>= f = f x
  Nothing >>= _ = Nothing

其中 Fuctor 就是 Functor...

class Category (c :: * -> * -> *) where
  id :: c a a
  (.) :: c y z -> c x y -> c x z

Category 就是一个范畴：

一个图有两样东西：对象、箭头
一个半群（Semigroup）满足两个定律：
封闭律：对于所有箭头 f g，都有箭头 h = f . g
结合律：(f .g) x = f . (g . x)
当然这个 (.) 不需要理解，是什么看上面的

class Semigroup a where
  (<>) :: a -> a -> a
  (<>) = mappend

一个含宏半群包含一个宏元 id：

class Semigroup a => Monoid a where
  mempty :: a

Monoid 也是一个范畴

Functor 是对象为范畴的范畴上的箭头：

class (Category c, Category d) => Functor c d t where
  fmap :: c a b -> d (t a) (t b)

这里 c 就是 Category 这个 typeclass 的

c :: * -> * -> *

它是一个 Higher Kind, 接受一个类型、再接受一个类型，返回一个类型，或者说

c :: * -> * -> *
(c T) :: * -> *

Functor 就是不同范畴的映射关系，把 O 映射到 T(O)、~> 映射到 T(~>)
然后对象就是箭头弄出来的变化态射，所以直接 fmap 箭头就可以了？

one = 1 — 对象 "单元" "宏元"
addOne = (+1) — 箭头 (\x -> x+1)
addOne one — 2
addOne . addOne $ one — 3

然后就有 Endofunctor "自函子"，从一个范畴到同一个范畴的 Functor，它是一个范畴，对象是 Category、箭头是 Cateogry 之间的态射

type Endofunctor c t = Functor c c t

然后就有 Monad 了...

class Endofunctor c t => Monad t where
  eta :: c a (t a)
  mu :: c (t (t a)) (t a

这里 t 是 (t :: * -> *), 它把一个对象 Map 到一个对象，这里是一个新 Monad

定义有点区别，Haskell 的 Control.Monad 是

class Applicative m => Monad m

而不是 Endofunctor, 不过 Applicative 其实是

class Functor f => Applicative f

反正 Monad、Applicative 都是 Haskell 完成 "sequence computations and combine their results" 的东西...
毕竟 Haskell 是基于『那种』函数式的（而不是类似 Scheme 的逻辑即『组合函数』函数式，使用递归、允许副作用）（Haskell 就换成了基于范畴论的函数式... 这是不能引入副作用的，而 Scheme 的抽象级别没有那么高，还能看出点机器化的东西）

不过说起来我也没写过『顺序应用函数』的 R6RS Scheme 程序... 因为我不是特别擅长 Scheme

不过看起来是可以的，反正 Scheme 里少说还有『参数顺序求值』

Racket: 4.14.1 Sequences

(define (histogram vector-of-words)
    (define a-hash (make-hash))
    (for ([word (in-vector vector-of-words)])
      (hash-set! a-hash word (add1 (hash-ref a-hash word 0))))
    a-hash)

Haskell 惰性求值不能保证

34 viewsduangsuse ¯\_(ツ)_/¯ | ∈ [E²PROM, 范畴论|单子], edited 13:22