Wyniki wyszukiwania - BazTech

1

Enumeration of words in context-free languages using Haskell

Wieczorek W.

Studia Informatica

|

2017

|

Vol. 38, nr 1B

5--17

EN

The cross-section enumeration problem is to list all words of length n in a language L in lexicographic order. We present the Haskell implementation of an algorithm for the cross-section enumeration problem for any language defined by a context-free grammar without unit productions and without λ-productions.

PL

Jednym z rozważanych problemów kombinatorycznych jest wyliczenie w porządku leksykograficznym wszystkich słów o długości n należących do pewnego języka L. W niniejszym artykule zaprezentowano algorytm – wraz ze stosownym kodem w języku Haskell – służący do takiego wyliczania. Zakładamy, że język L zdefiniowany jest za pomocą gramatyki bezkontekstowej bez produkcji jednostkowych i bez λ-produkcji.

2

Monadic Printing Revisited

Grzanek K.

Journal of Applied Computer Science Methods

|

2016

|

Vol. 8 No. 1

66--79

EN

Expressive and clear implementation of monadic printing requires an amount of work to define and design proper abstractions to rely upon when performing the actual programming works. Our previous realization of tree printing library left us with a sense of lack with respect to these considerations. This is why we decided to re-design and re-implement the library with core algorithms based upon new, effective and expressive text printing and concatenation routines. This paper presents the results of our work.

3

Monadic Tree Print

Grzanek K.

Journal of Applied Computer Science Methods

|

2014

|

Vol. 6 No. 2

147--157

EN

Directed acyclic graphs and trees in particular belong to the most extensively used data structures. Visualizing them properly is a key to a success when developing complex algorithms that make use of them. Textual visualizations a la UNIX tree command is essential when the urge is to deal with large trees. Our aim was to design a library that would exploit this approach and to make an implementation of it for a purely functional programming language. The library uses monads to print directly into an output stream or to generate immutable Strings. This paper gives a detailed overview of the solution.

4

The Impact of seq on Free Theorems-Based Program Transformations

Johann P., Voigtländer J.

Fundamenta Informaticae

|

2006

|

Vol. 69, nr 1,2

63-102

EN

Parametric polymorphism constrains the behavior of pure functional programs in a way that allows the derivation of interesting theorems about them solely from their types, i.e., virtually for free. Unfortunately, standard parametricity results - including so-called free theorems - fail for nonstrict languages supporting a polymorphic strict evaluation primitive such as Haskell's seq. A folk theorem maintains that such results hold for a subset of Haskell corresponding to a Girard-Reynolds calculus with fixpoints and algebraic datatypes even when seq is present provided the relations which appear in their derivations are required to be bottom-reflecting and admissible. In this paper we show that this folklore is incorrect, but that parametricity results can be recovered in the presence of seq by restricting attention to left-closed, total, and admissible relations instead. The key novelty of our approach is the asymmetry introduced by left-closedness, which leads to ``inequational'' versions of standard parametricity results together with preconditions guaranteeing their validity even when seq is present. We use these results to derive criteria ensuring that both equational and inequational versions of short cut fusion and related program transformations based on free theorems hold in the presence of seq.