Hackage :: [Package]

HyloDP: A package for solving dynamic programming problems in Haskell

[ bsd3, dynamic-programming, library, program, recursion ] [ Propose Tags ]

This package contains the library HyloDP for solving dynamic programming problems in Haskell, and six solved DP problems: Edit Distance, Fibonacci, Knapsack, Longest Common Subsequence, Random Walk and Text Segmentation.

The library HyloDP implements the code of the research article:

'Easily solving dynamic programming problems in Haskell by memoization of hylomorphisms' by D.Llorens and J.M. Vilar. Software: Practice and Experience (ISSN:1097-024X). 2020; 50: 2193–2211.

A preliminary version of the article can be downloaded from here.

[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 1.0.0
Change log CHANGELOG.md
Dependencies base (>=4.7 && <5), containers (>=0.6 && <0.7), HyloDP, MemoTrie (>=0.6.11 && <0.7) [details]
License BSD-3-Clause
Copyright David Llorens and Juan Miguel Vilar, 2020
Author David Llorens <dllorens@uji.es>, Juan Miguel Vilar <jvilar@uji.es>
Maintainer David Llorens <dllorens@uji.es>
Category Recursion, Dynamic Programming
Home page https://github.com/DavidLlorens/HyloDP
Source repo head: git clone https://github.com/DavidLlorens/HyloDP.git
Uploaded by DavidLlorens at 2024-01-17T10:03:49Z
Distributions NixOS:1.0.0
Executables LongestCommonSubsequenceMain, RandomWalkMain, KnapsackMain, TextSegmentationMain, FibonacciMain, EditDistanceMain
Downloads 54 total (6 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2024-01-17 [all 1 reports]

Readme for HyloDP-1.0.0

[back to package description]

HyloDP

A package for solving dynamic programming problems in Haskell

Introduction

This package contains the library HyloDP and six solved DP problems: Edit Distance, Fibonacci, Knapsack, Longest Common Subsequence, Random Walk and Text Segmentation.

This package contains the code of the research article: Software: Practice and Experience (ISSN:1097-024X)

"Easily solving dynamic programming problems in Haskell by memoization of hylomorphisms" by D.Llorens and J.M. Vilar. Software: Practice and Experience (ISSN:1097-024X). 2020; 50: 2193–2211. https://doi.org/10.1002/spe.2887.

A preliminary version of the paper can be downloaded from here.

The core ideas are:

  • Using hylomorphisms as generic control flow mechanism.

  • Adding memoization to avoid recomputation of intermediate results.

  • Modelling the composition of solutions by means of semirings.

  • Using dispatch by result type as a simple way to decide the kind of answer desired (e.g. the best solution, the score of that solution, or the total number of solutions.)

A problem is described by an instance of DPProblem and solved by using dpSolve. See the documentation of HyloDP.Base for an example.

Contents

  • The library is contained in the src directory.
  • The test directory contains several HSpec tests.
  • There are six examples in the examples directory.
  • The run-examples.sh script runs all the examples.
  • This library is implemented as a package on Hackage.