1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
------------------------------------------------------------------------------
--- This library defines a data structure for sequence of values.
--- It is used in search trees (module `SearchTree`) as well as in
--- set functions (module `SetFunctions`).
--- Using sequence of values (rather than standard lists of values)
--- is necessary to get the behavior of set functions
--- w.r.t. finite failures right, as described in the paper
---
--- > J. Christiansen, M. Hanus, F. Reck, D. Seidel:
--- > A Semantics for Weakly Encapsulated Search in Functional Logic Programs
--- > Proc. 15th International Conference on Principles and Practice
--- > of Declarative Programming (PPDP'13), pp. 49-60, ACM Press, 2013
---
--- Note that this is a simple implementation for PAKCS in order to provide
--- some functionality used by other modules.
--- In particular, the intended semantics of failures is not provided
--- in this implementation.
---
--- @author  Fabian Reck, Michael Hanus
--- @version February 2016
--- @category algorithm
------------------------------------------------------------------------------

module ValueSequence(ValueSequence, emptyVS, addVS, failVS, (|++|), vsToList)
 where

--- A value sequence is an abstract sequence of values.
--- It also contains failure elements in order to implement the semantics
--- of set functions w.r.t. failures in the intended manner (only in KiCS2).
data ValueSequence a = EmptyVS | ConsVS a (ValueSequence a)

--- An empty sequence of values.
emptyVS :: ValueSequence a
emptyVS = EmptyVS

--- Adds a value to a sequence of values.
addVS :: a -> ValueSequence a -> ValueSequence a
addVS = ConsVS

--- Adds a failure to a sequence of values.
--- The argument is the encapsulation level of the failure.
failVS :: Int -> ValueSequence a
failVS _ = EmptyVS -- cannot be implemented in PAKCS!"

--- Concatenates two sequences of values.
(|++|) :: ValueSequence a -> ValueSequence a -> ValueSequence a
xs |++| ys = case xs of EmptyVS     -> ys
                        ConsVS z zs -> ConsVS z (zs |++| ys)

--- Transforms a sequence of values into a list of values.
vsToList :: ValueSequence a -> [a]
vsToList EmptyVS       = []
vsToList (ConsVS x xs) = x : vsToList xs