Smap

Choose the version you want to view.

Current version:Version message:

More comments and type signatures

Click on a tag to show all related programs.

curry functional list logic

Click on the badge to open the comment window for viewing and writing comments.

No comments yet.

Created by mh on April 10, 2014 (last modified on September 4, 2020)

0 users favorited this

Description: Sorting a list by finding a sorted permutation

Source code (Latest version):

-- This is an example for the use of non-deterministic operations
-- in a Curry program.

-- We want to sort a list by selecting a sorted permutation.

-- First, we define the non-deterministic insertion of an
-- element into a list. An element can be inserted into a list
-- either at the fron (first rule) or into the tail of a list
-- (second rule).
ndinsert :: a -> [a] -> [a]
ndinsert x ys     = x : ys
ndinsert x (y:ys) = y : ndinsert x ys

-- A permutations of a list can be obtained by non-deterministically
-- inserting the first element into some permutation of the
-- remaining elements
perm :: [a] -> [a]
perm []     = []
perm (x:xs) = ndinsert x (perm xs)

-- Next we define a partial predicate which evaluates to True
-- if the argument list is sorte, i.e., if all elements are in ascending order.
sorted :: Ord a => [a] -> Bool
sorted []              = True
sorted [_]             = True
sorted (x:y:ys) | x<=y = sorted (y:ys)

-- Sorting a list means finding a sorted permutation of it:
sort :: Ord a => [a] -> [a]
sort xs | sorted ys = ys
  where ys = perm xs

-- Sorting an example list:
main = sort [4,1,2,6,5,3]

Options

Versions

2 versions

Tags

4 tags

Comments

0 comments »

Permutation sort

implemented in Curry