Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Левая развёртка косписков, anyone?

Код ниже на современном (с arrow functions - это ES5?) джаваскрипте. У натуральных чисел и списков есть, кроме обычного катаморфизма, такая же "штука с алгеброй", но "хитрая", соответствующая левой свёртке:
natCata = (algebra, i) => {

        if (i == 0)
	{
		return algebra(null)
	}
	else
	{
		return algebra(natCata(algebra, i - 1))
	}
}

natCata2 = (algebra, i) => {

	var ret = algebra(null) 
	while (i-- > 0)
	{
		ret = algebra(ret)
	}
	return ret
}
Вот у меня 3 вопроса в связи с этим:
1. Какие ещё структуры обладают этим "левым катаморфизмом"? Должны быть линейными, а ля

data O a = O a (E a) | ONil
data E a = E a (O a) | ENil

и неизоморфными хитрым спискам. Например O a неизоморфен списку из data RR a = OO a | EE a

2. Выразимы ли эти "периодические верёвки" как фиксированные точки функторов? Как вообще выглядит всё это разнообразие верёвок, т.е. какие варианты возможны? вот один, выразимый фиксированной точкой: data XList a b = XCons a (Xlist a b) | XNil b

3. Есть ли дуально "хитрые штуки с коалгеброй", у каких структур данных, и чему они соответствуют.
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments