Producing all ideals of a forest, functionally

Jean Christophe Filliâtre; François Pottier

doi:10.1017/S0956796803004763

Producing all ideals of a forest, functionally

Jean Christophe Filliâtre, François Pottier

Research output: Contribution to journal › Article › peer-review

Abstract

We present functional implementations of Koda and Ruskey's algorithm for generating all ideals of a forest poset as a Gray code. Using a continuation-based approach, we give an extremely concise formulation of the algorithm's core. Then, in a number of steps, we derive a first-order version whose efficiency is comparable to that of a C implementation given by Knuth.

Original language	English
Pages (from-to)	945-956
Number of pages	12
Journal	Journal of Functional Programming
Volume	13
Issue number	5
DOIs	https://doi.org/10.1017/S0956796803004763
Publication status	Published - 1 Sept 2003
Externally published	Yes

Access to Document

10.1017/S0956796803004763

Cite this

@article{54349d5f3e9146b4869622096c5f55fd,

title = "Producing all ideals of a forest, functionally",

abstract = "We present functional implementations of Koda and Ruskey's algorithm for generating all ideals of a forest poset as a Gray code. Using a continuation-based approach, we give an extremely concise formulation of the algorithm's core. Then, in a number of steps, we derive a first-order version whose efficiency is comparable to that of a C implementation given by Knuth.",

author = "Filli{\^a}tre, \{Jean Christophe\} and Fran{\c c}ois Pottier",

year = "2003",

month = sep,

day = "1",

doi = "10.1017/S0956796803004763",

language = "English",

volume = "13",

pages = "945--956",

journal = "Journal of Functional Programming",

issn = "0956-7968",

number = "5",

}

TY - JOUR

T1 - Producing all ideals of a forest, functionally

AU - Filliâtre, Jean Christophe

AU - Pottier, François

PY - 2003/9/1

Y1 - 2003/9/1

N2 - We present functional implementations of Koda and Ruskey's algorithm for generating all ideals of a forest poset as a Gray code. Using a continuation-based approach, we give an extremely concise formulation of the algorithm's core. Then, in a number of steps, we derive a first-order version whose efficiency is comparable to that of a C implementation given by Knuth.

AB - We present functional implementations of Koda and Ruskey's algorithm for generating all ideals of a forest poset as a Gray code. Using a continuation-based approach, we give an extremely concise formulation of the algorithm's core. Then, in a number of steps, we derive a first-order version whose efficiency is comparable to that of a C implementation given by Knuth.

U2 - 10.1017/S0956796803004763

DO - 10.1017/S0956796803004763

M3 - Article

AN - SCOPUS:0042411217

SN - 0956-7968

VL - 13

SP - 945

EP - 956

JO - Journal of Functional Programming

JF - Journal of Functional Programming

IS - 5

ER -

Producing all ideals of a forest, functionally

Abstract

Access to Document

Fingerprint

Cite this