#info #Telegram 这周 duangsuse 将开始使用一种新的制度，可能可以提升我的工作效率和身体素质（目前应该视为首要任务） —

现在，很多东西对于 duangsuse 来说终于不是难题了，duangsuse 已经有了可以在应用层（包括异步、函数式、用户界面、计算机网络、数据库、IO 等）驰骋的能力，而且还是多语言！

所以我依然要继续学习 #CS 计算机科学了（而不是成天等着完成 XX 事情），

不过，我决定，因为每周的时间非常有限， 一周只完成大概的两件任务（任务是随便定的）

然后剩下的时间就主要是咸鱼看番（ 🐟
（算是对完成速度快的鼓励
（好吧，是因为我目前好像不应该在电脑面前坐太久呢。

#algorithm #cs #net #security 🌚

这... 他们也真是太有创意了，这都能想出来（其实也不意外，像这种增加服务资源消耗的破坏性攻击也是直觉所在了...）

🤔 HashMap 的最差时间复杂度，假设是扎堆的情况下可能是 O(n**2) ？
看来还是我不了解这些算法....

我一直以为最差大不了就是 O(n) 的，线性 Map 也就是这个复杂度：

#Haskell 里，（List）Map 可以这么定义：

data ListMap k a = ListMap [(k, a)] deriving Show

Eq

不能直接 derive。
然后我们定义基础的 get 和 put 操作：

import Data.Maybe (listToMaybe)

getKey :: (Eq k) => ListMap k a -> k -> Maybe a
getKey (ListMap xs) k = (snd <$>) . listToMaybe . find $ xs
where
find = filter ((== k) . fst)

putKey :: ListMap k a -> k -> a -> ListMap k a
putKey (ListMap kvs) k v = ListMap ((k, v) : kvs)

因为 Haskell 多了一层递归调用栈的空间复杂度（比如 filter 操作）... 算了，有 TCO... 算了... 和时间复杂度无关...

😫

但是，即使是 ArrayMap 的最差情况时间复杂度也只是 O(n) 啊！为啥 HashMap 就多了一个 n*...

我知道，现在流行的（比如，Lua 和 Ruby 和 PHP 的实现）散列表实现都是基于『散列桶』分配的，需要时多分配一些桶（链表），重新算散列分配操作

但那的复杂度好像也不是 O(n**2) 啊... 毕竟最差情况也就是算一次 O(1) 的散列 Key 拿储蓄对象的 bin，结果 bin 里碰撞了（不止一个 kv 被分配在某桶），那复杂度就会是 O(n) （要线性查找一遍）

什么是哈希洪水攻击（Hash-Flooding Attack）？

「『哈希表的最差时间复杂度是 n^2』——这是一项所有软件开发人员烂熟于心的基础知识，所有人都知道，但是所有人都只是看过一眼就忘在脑后了。直到 2003 年，才第一次有人提出可以用这个东西发动网络攻击，而且效果十分之出色。」

https://www.zhihu.com/question/286529973/answer/676290355

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 惰性求值不能保证

#FP #CS #Haskell 然后这里有一些 Monad:

newtype Identity a = Identity { runIdentity :: a }

+ Haskell 不会写 Monad 怎么编程？把 Haskell 写成 Scheme？有点困难啊，因为 Haskell 不像 Scheme 还是『有点节操』的函数式（只是组合函数而不是把一切都看成函数组合...）
+ 这是我从某范畴论教程上抄下来的（虽然完全是我默写下来的...）
+ 使用 newtype 而不是 data 是因为 Identity 是同构类型

+ 如果使用 data 会是这样的：

data Identity a = Identity { runIdentity :: a }
data Identity a where
  Identity :: a -> Identity a

+ runIdentity :: Identity a -> a 和 Identity 构造器的类型 (Identity :: a -> Identity a) 是同构的
+ 同构是指有一个 f :: a -> b 的同时也有 f' :: b -> a
比如说，f = show :: Int -> String; f' = toInt :: String -> Int
这就是说 (f . f') = id = (f' . f)

然后可以去写 Functor Instance

instance Functor (Identity :: * -> *) where
fmap :: (a -> b) -> (Identity a -> Identity b)
fmap f (Identity i) = Identity <$> f i

这里 i :: a，直接模式匹配把 a 取出来了

instance Monad Identity where
return x = Identity x
Identity x >>= f = f x

然后还有比较常用的 Maybe 和 Either 和新学到的 Reader Monad

data Maybe a where
  Just :: a -> Maybe a
  Nothing :: Maybe a
  deriving (Eq, Show)

instance Functor (Maybe :: * -> *) where
  fmap :: (a -> b) -> (Maybe a -> Maybe b)
  fmap f (Just x) = (Just . f) $ x
  fmap f Nothing = Nothing

instance Monad Maybe where
  return :: a -> Maybe a
  return = Just
  (>>=) :: Maybe a -> (a -> b) -> b
  (Just x) >>= f = f x
  Nothing >>= f = Nothing

... 我还是不知道 mu :: t t a -> t a 使用在哪里... 但是 (>>=) 说不定使用了它，因为 f x 是 b，但是 Nothing 是 Maybe a 呢，就是说要先 Map 到 Maybe Maybe a 才用 mu :: Maybe Maybe a -> Maybe a 弄回来就可以了？

data Either a b = Left a | Right b deriving (Eq, Show)

这里 Either a b 是 a 和 b 的 Product Type

Coproduct: 有 Left 箭头从 a 到达 Either a b ；Right 箭头从 b 到达 Either a b
有一个 (Left :: a -> Either a b) Constructor
和一个 (Right :: b -> Either a b ) 构造器
反过来就是 Product: 比如 (\(Left l) = l) :: Either a b -> a （这里为了方便没有考虑还有 Right 解构器的事情；实际上这是不对的，导致不是所有 Either 值都能被这个 Operator 解构）
从 Either a b 到达 a (箭头就是 (->) Haskell 的中缀类型构造器）

instance Functor (Either a) where

  fmap _ (Left l) = Left l
  fmap f (Right r) = Rigth $ f r

就是 mapRight

instance Monad (Either a) where
  Left l >>= f = Left l
  Right r >>= f = f r

此外，一般还定义这些函数：

either :: Either a b -> (a -> a') -> (b -> b') -> Either a' b'
either (Left l) f _ = Left $ f l
either (Right r) _ g = Right $ f r

好吧... 这好像是 Map 两边的...

either :: (a -> c) -> (b -> c) -> Either a b -> c
either f g (Left x) = f x
either f g (Right x) = g x

其实是

一般还会有 (isLeft :: Either a b -> Bool)、(asLeft :: Either a b -> Maybe a)、swap :: Either a b -> Either b a、flatMapLeft :: Either a b -> (a -> c) -> c 什么的

然后就是 Reader

它的作用就是给一个计算 fun :: t -> a 喂一个 t，拿到一个 a



newtype Reader t a = Reader { runReader :: (t -> a) }

这里 runReader :: Reader t a -> (t -> a)
然后我们去 instance Functor 和 Monad 它

instance Functor (Reader t) where
  fmap f (Reader r) = Reader $ \i -> f (r i)

instance Monad (Reader t) where
  return x = Reader (\_ -> x)
  (Reader r) >>= f = Reader $ \r' -> runReader r' (f (r r'))

有点难于理解，看看怎么用的...

然后还有推荐的 Cont、ST Monad、Free、Alternative

Cont 就是 CPS Monad
CPS 就是 Continuation Passing Style

比如有一个 Operator add :: Int -> Int -> Int
然后你定义一个 add2 :: Int -> Int


add2 x = add x 2 — x + 2

但是就不能进行其他的计算了（不允许嵌套的话），比如 (putStrLn . show) :: a -> IO () 当然在这里 a 是 (Num a) => Context 下

但是可以去 CPS, 假设就有一个 excited :: Int -> IO () 的东西

add2Cps x = excited (add x 2)

计算就可以在 excited 函数里继续

其他的以后我会学的，顺便再学学 Scala 里怎么写... Haskell 是门好语言

接上文

newtype Reader t a = Reader { runReader :: (t -> a) }

instance Functor (Reader t) where
  fmap f (Reader r) = Reader $ \i -> f (r i)

instance Monad (Reader t) where
  return x = Reader (\_ -> x)
  (Reader r) >>= f = Reader $ \r' -> runReader r' (f (r r'))

doHello :: Reader String String
doHello r = asks >>= \s ->
return "Hello " ++ s

hello = runreader doHello "duangsuse"

... 弄了半天以后，最后我的实现... 深感面向类型编程啊，类型简直是救星（因为我之前没有写过这种东西，是第一次，居然利用类型写出来了能用的）

好耶！duangsuse 的第一个 Monad instance！

下面是 CPS Monad：

比如有一个 Operator add :: Int -> Int -> Int
然后你定义一个 add2 :: Int -> Int


add2 x = add x 2 — x + 2

但是就不能进行其他的计算了（不允许嵌套的话），比如 (putStrLn . show) :: a -> IO () 当然在这里 a 是 (Num a) => Context 下

但是可以去 CPS, 假设就有一个 excited :: Int -> IO () 的东西

add2Cps x = excited (add x 2)
  where excited n = putStrLn . (++ "👓") . show

计算就可以在 excited 函数里继续（一言不合就 🐸...

这样的 add2Cps 就是 add2Cps :: Int -> (Int -> r) -> r

它把计算的结果传给另一个函数 (t -> r) 然后自己再返回 r

这样就是：

newtype Cont t r = Cont { runCont :: (t -> r) -> r }

然后可以把 excited 的 add2Cps 改成 Cont Monad 的形式

add2Cps :: Int -> Cont Int (IO ())
add2Cps x = return x +2

然后 instance Monad

instance Monad (Cont t) where
  return x = \_ -> Cont ($ x)

(Cont c) >>= k = Cont $ \tr -> c $ \a -> runCont (k a) tr

使用 add2Cps 实际上就是

runCont (add2Cps 2) (putStrLn. show)
= runCont (

return 2 +2

) (putStrLn . show)
= runCont (

Cont ($ 4)

) ((putStrLn . show) :: Int -> IO ())
= Cont ($ 4) >>= (putStrLn . show)
= Cont $ \tr -> runCont (Cont ($ 4)) >>= (\a -> runCont (putStrLn . show a)) tr

ST, Alternative, Free 都有点高级了，我还不会，算...

明天，我会讲一些关于 ES6 的事情，可能包括模板、async 函数、Generator 函数和 async 函数的关系（为啥 Generator 函数可以用来实现异步操作组合？）

应用层已经阻止不了 duangsuse 了（显然，我已经基本了解了所有 pattern，回调和事件监听（包括 Observable）、基于消息队列的发布订阅（Tk 的 bind/event_generate, Qt/GTK 的信号和插槽、.NET 的 Event）、Promise、 Async 函数

🌚

希望以后 duangsuse 能做到：不被应用层的人鄙视的程度。

这周的任务：

+ 默写 C# BitMap 反色算法
+ ES6 重写 sm.ms js 库（虽然原来也有用 ES6 特性）

#Haskell duangsuse 日常 Haskell.... 🤔...

#Docker:

想想了关键字...

MAINTAINER
FROM [AS ...]
ADD
ENV
WORKDIR
RUN
EXEC
CMD
COPY [—FROM ...]
ENTRYPOINT

#archlinux #linux #sysadmin https://github.com/Trumeet/GPartArch

其实我不会 sed，不太会写 bash 脚本（当然如果我要重写，这里不需要我会写任何东西，因为都是 mkarchiso 项目提供的可能
我也没有用过 mkarchiso

我也不是很了解 Linux 的 isolinux, syslinux 引导加载机制，也不清楚 ramfs 和 initcpio 那些东西...

pacman 我用过，我曾经是 Archlinux 的用户，不过说到完全理解也未必，但基本的依赖关系、AUR、Package Group、Signature、Repository、Mirrors 什么的和 native 层动态链接什么的也都还清楚，不清楚也可以看 ArchWiki

不过说到定制版 LiveCD，我的确做过一个，并且在学校使用过，那时候是在一个老 x86 台式机上 Linux Mint + Remastersys 做的，当时加了不少软件，可惜当时我啥都不懂...

不过也很好用就是了

不管怎么样，看起来，对于一个 Unix 系系统管理员来说，维护自己的发行版可能是最大佬的程度了...

还得自己再去写类似 Pacman, Portage 这种工具... 还要管理自己的根目录架构和软件包结构... 还有系统的定制化，systemd、引导加载、发布 LiveCD iso...

#sysadmin 🤔 那我先默写下 这个

说起来，我写的第一个真正意义上的程序其实就是 Bash 写的...

do_install() { printf "Installing... \t"; apt install -y imagemagisk bc schedtools ccache }
check_do_install() {
printf "Docker tag: " $DOCKER_TAG
if [ $DOCKER_TAG = "extra-latest" ]
then; do_install
else; printf "Skipping...\n"; fi
}

main() {
if [ $1 = "auto" ]
then; check_do_install
else; do_install
fi
}

main $*

#Android 希望入门了解 Android 的服务接口什么的架构呢，以后有希望的话，我要重写这些：

+ https://github.com/Trumeet/WorkMode
+ https://github.com/Trumeet/SysUIController/tree/master/app/src/main/java/moe/yuuta/sysuicontroller

虽然我平时作为后端也是会涉及到二进制流处理的... 但是看起来 AIDL 和 Paracelabel 也是值得学的，可是我之前是 Intents 都不是特别了解，现在知道了.,..

#net #Haha #life 🌚 自建 METO DNS...

好吧... 是要你自己修改 hosts 解析哦...

curl 124.156.193.111 -H "Host: tld.meto"

⛰ 具有自主知识产权的 .meto 域名上线

目前还在筹集 (piàn) 资金 (qián)，开放了一个 demo 页以便公众进行体验（疯狂狗头

https://tld.i-meto.com/help.html
https://t.me/metooooo/1727