August 25th, 2013

Book

Что такое linked list

Я тут понял, что от нас скрывали! Linked list в крестиках и сишечке - это вот такая штука:
newtype Node a b = Node (Maybe (a, b)) deriving (Functor, Show)

type List a = Fix (Node a)

data Vars a = Vars { l :: Int, p :: List a }

length :: List a -> Int
length pp = while 
	(Vars { l = 0, p = pp})
	(notNull . p) 
	(\env -> Continue $ env { l = l env + 1, p = next $ p env }) 
	l
В Сишечке идиоматические sum types бывают только двух частных видов - энумы и т.н. указатели. У энумов, как и полагается, все конструкторы 0-арные. Указатели - это аналог Maybe. Произведения есть (структы). Есть ограниченная форма фиксированных точек функторов, на которых строятся т.н. связные структуры. Вот пример связного списка:

newtype Node a b = Node (Maybe (a, b))
type List a = Fix (Node a)

По содержанию это тот же самый Fix (\X -> 1 + A * X), но выбранная форма не содержит отсутствующих в языке полноценных сумм и фиксированных точек: только произведения, указатель и фиксированная точка как раз в той форме, которая есть. (a, b) описывается "структурой":
template <typename A, typename B> 
struct List 
{
	A item;
	B next;
}
Maybe (a, b) - это указатель на структуру: List<A, B> * в их записи. Node пропускаем, т.к. это пустышка. Fix (Node a) - это List<A, B> *, где B = List<A, B> *. Как и Хаскель, их запись не позволяет сделать такого напрямую, но есть специальный трюк:
template <typename A> 
struct List 
{
	A item;
	List<A> * next;
}
В результате сумм нету, а списки есть! Голь на выдумки хитра!
Book

Вторая версия

{-# LANGUAGE NoMonomorphismRestriction, DeriveFunctor #-}

import Data.Functor.Foldable

data NodeBase a b = NodeBase 
	{ item :: a
	, next :: b 
	} deriving (Functor, Show)
newtype ListBase a b = ListBase (Maybe (NodeBase a b)) deriving (Functor, Show)

type ListPtr a = Fix (ListBase a)
type ListNode a = ListBase a (ListPtr a)

nil = Fix . ListBase $ Nothing
cons a b = Fix . ListBase . Just $ NodeBase a b