-
Quicksort in Haskell
The quicksort algorithm is a beautiful algorithm that has been used in introductions to the elegance and simplicity of functional programming. Compared with the implementation in C/C++, the Haskell code below is short and looks elegant:
-
Functor, Applicative and Monad
Functor, Applicative 和 Monad 的数学定义：
- A functor is a type of mapping between categories, a functor is a morphism from a source category to a target category.
- An applicative functor is a strong lax monoidal functor.
- A monad is an endofunctor (a functor mapping a category to itself), together with two natural transformations.
-
Non-constructive proof of existance
在 A Course in Discrete Structures by Rafael Pass and Wei-Lung Dustin Tseng 上看到一个很有意思的证明方法：Non-constructive proof of existance。
-
Proof by Contradiction
Proof by Contradiction is an important proof skill that: in order to proof $\Phi$, and $\neg \Phi$ as a new given, and attempt to deduce an evidently false statement($\bot$).
In a schema:
- Given: $\dots$
- To be proved: $\Phi$
- Proof:
- Suppose $\neg \Phi$
- To be proved: $\bot$
- Proof: $\dots$
- Thus $\Phi$.
-
Variadic Functions
编程语言对于 Variadic function 的支持极大地扩展了语言的表达能力，对Haskell这样类型系统及其强大的语言，Variadic Function 的实现更是优雅。
-
代数基本概念
代数学的基本概念。
-
使用FFT和DCT进行图片压缩
使用二维离散傅里叶变换或二维离散余弦变换可以得到图片的频率分布（频谱），在此基础上过滤调高频信号，然后进行离散傅里叶反变换或者离散余弦反变换 可以得到压缩后的图片。
-
Fixed point and the Y combinator
不动点(Fixed-point)指的是 $f(x)$ 的定义域内的一个点 $c$ 是函数 $f(x)$ 的不动点，当且仅当 $c$ 满足：
\[f(c) = c\]Fixed-point Combinator 指的是一个高阶函数 $y$ 满足
\[\forall f: y\ f = f\ (y\ f)\]也就是说，如果令 $x = y\ f$ 那么
\[x = f\ x\]Fixed-point Combinator 是一个用于求函数的不动点的高阶函数，接受一个函数作为参数，并且返回一个函数。 $y\ f$ 表示函数 $f$ 的一个不动点。通过不动点组合子，可以实现通过非递归的 Lambda 表达式来定义匿名的递归函数。
Y Combinator 是 Haskell B. Curry 发现的一种不动点组合子，定义为
\[Y := \lambda f.\ (\lambda x.\ f\ (x\ x))\ (\lambda x.\ f\ (x\ x))\] -
C++ 实现 Currying 和 Partial application
Curry 和 Partical application 是高阶函数的一个特点，在函数式编程中有着重要的应用。 借助 C++11 的变长参数模板(Variadic template)，可以在 C++ 中实现 Currying 和 Partial application。
-
Tak函数和Tarai函数的性能
Tak函数和Tarai函数是两个非常类似，但本质上差异显著的函数，具体的定义参考Wikipedia 的页面。
- Tak 函数
It is defined as follows:
\[\tau (x,y,z) = {\begin{cases} \tau (\tau (x-1,y,z), \tau (y-1,z,x), \tau (z-1,x,y)) & {\text{if }}y < x \\ z & {\text{otherwise}} \end{cases}}\]John McMarchy 的论文 An Interesting Lisp Function 中论述了以下两个 tak 函数的性质。
\[tak(x+a, y+a, z+a) = tak(x, y, z) + a\]以及
\[tak(x, y, z) = \text{ if } x \le y \text{ then } y \text{ else if } y \le z \text{ then } z \text{ else } x\]- Tarai 函数
2016-01
2015-12
Subscribe via RSS