Remove duplicate elements: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) m (fix markup) |
m (→{{header|Wren}}: Minor tidy) |
||
| (39 intermediate revisions by 14 users not shown) | |||
Line 498:
<syntaxhighlight lang="applescript">{1, 2, 3, "a", "b", "c", 4, {b:"c"}, {"c"}, "d"}</syntaxhighlight>
=={{header|
<syntaxhighlight lang="rebol">arr: [1 2 3 2 1 2 3 4 5 3 2 1]
print unique arr</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5</pre>
=={{header|ATS}}==
=== ATS2 implementation for values having an ''equality'' predicate ===
This method runs no worse than O(n*n) in the number of elements. It is an example of the brute-force technique.
The implementation is for non-linear types, only. I implement the predicate as a non-linear closure.
<syntaxhighlight lang="ats">
(* Remove duplicate elements.
This implementation is for elements that have an "equals" (or
"equivalence") predicate. It runs O(n*n) in the number of
elements. *)
#include "share/atspre_staload.hats"
(* How the remove_dups template function will be called. *)
extern fn {a : t@ype}
remove_dups
{n : int}
(eq : (a, a) -<cloref> bool,
src : arrayref (a, n),
n : size_t n,
dst : arrayref (a, n),
m : &size_t? >> size_t m)
:<!refwrt> #[m : nat | m <= n]
void
(* An implementation of the remove_dups template function. *)
implement {a}
remove_dups {n} (eq, src, n, dst, m) =
if n = i2sz 0 then
m := i2sz 0
else
let
fun
peruse_src
{i : int | 1 <= i; i <= n}
{j : int | 1 <= j; j <= i}
.<n - i>.
(i : size_t i,
j : size_t j)
:<!refwrt> [m : int | 1 <= m; m <= n]
size_t m =
let
fun
already_seen
{k : int | 0 <= k; k <= j}
.<j - k>.
(x : a,
k : size_t k)
:<!ref> bool =
if k = j then
false
else if eq (x, dst[k]) then
true
else
already_seen (x, succ k)
in
if i = n then
j
else if already_seen (src[i], i2sz 0) then
peruse_src (succ i, j)
else
begin
dst[j] := src[i];
peruse_src (succ i, succ j)
end
end
prval () = lemma_arrayref_param src (* Prove 0 <= n. *)
in
dst[0] := src[0];
m := peruse_src (i2sz 1, i2sz 1)
end
implement (* A demonstration with strings. *)
main0 () =
let
val eq = lam (x : string, y : string) : bool =<cloref> (x = y)
val src =
arrayref_make_list<string>
(10, $list ("a", "c", "b", "e", "a",
"a", "d", "d", "b", "c"))
val dst = arrayref_make_elt<string> (i2sz 10, "?")
var m : size_t
in
remove_dups<string> (eq, src, i2sz 10, dst, m);
let
prval [m : int] EQINT () = eqint_make_guint m
var i : natLte m
in
for (i := 0; i2sz i <> m; i := succ i)
print! (" ", dst[i] : string);
println! ()
end
end
</syntaxhighlight>
{{out}}
<pre> a c b e d</pre>
=== ATS2 implementation for linear values having an ''equality'' predicate ===
This method runs no worse than O(n*n) in the number of elements. It is another example of the brute-force technique.
This implementation can handle elements of linear type. I implement the predicate as a template function.
There are two interfaces: one for an array, and one for a linked list.
<syntaxhighlight lang="ats">
(* Remove duplicate elements.
This implementation is for elements that have an "equals" (or
"equivalence") predicate. It runs O(n*n) in the number of
elements. It uses a linked list and supports linear types.
The equality predicate is implemented as a template function. *)
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
#define NIL list_vt_nil ()
#define :: list_vt_cons
(*------------------------------------------------------------------*)
(* Interfaces *)
extern fn {a : vt@ype}
array_remove_dups
{n : int}
{p_arr : addr}
(pf_arr : array_v (a, p_arr, n) |
p_arr : ptr p_arr,
n : size_t n)
:<!wrt> [m : nat | m <= n]
@(array_v (a, p_arr, m),
array_v (a?, p_arr + (m * sizeof a), n - m) |
size_t m)
extern fn {a : vt@ype}
list_vt_remove_dups
{n : int}
(lst : list_vt (a, n))
:<!wrt> [m : nat | m <= n]
list_vt (a, m)
extern fn {a : vt@ype}
remove_dups$eq :
(&a, &a) -<> bool
extern fn {a : vt@ype}
remove_dups$clear :
(&a >> a?) -< !wrt > void
(*------------------------------------------------------------------*)
(* Implementation of array_remove_dups *)
(* The implementation for arrays converts to a list_vt, does the
removal duplicates, and then writes the data back into the original
array. *)
implement {a}
array_remove_dups {n} {p_arr} (pf_arr | p_arr, n) =
let
var lst = array_copy_to_list_vt<a> (!p_arr, n)
var m : int
val lst = list_vt_remove_dups<a> lst
val m = list_vt_length lst
prval [m : int] EQINT () = eqint_make_gint m
prval @(pf_uniq, pf_rest) =
array_v_split {a?} {p_arr} {n} {m} pf_arr
val () = array_copy_from_list_vt<a> (!p_arr, lst)
in
@(pf_uniq, pf_rest | i2sz m)
end
(*------------------------------------------------------------------*)
(* Implementation of list_vt_remove_dups *)
(* The list is worked on "in place". That is, no nodes are copied or
moved to new locations, except those that are removed and freed. *)
fn {a : vt@ype}
remove_equal_elements
{n : int}
(x : &a,
lst : &list_vt (a, n) >> list_vt (a, m))
:<!wrt> #[m : nat | m <= n]
void =
let
fun {a : vt@ype}
remove_elements
{n : nat}
.<n>.
(x : &a,
lst : &list_vt (a, n) >> list_vt (a, m))
:<!wrt> #[m : nat | m <= n]
void =
case+ lst of
| NIL => ()
| @ (head :: tail) =>
if remove_dups$eq (head, x) then
let
val new_lst = tail
val () = remove_dups$clear<a> head
val () = free@{a}{0} lst
val () = lst := new_lst
in
remove_elements {n - 1} (x, lst)
end
else
let
val () = remove_elements {n - 1} (x, tail)
prval () = fold@ lst
in
end
prval () = lemma_list_vt_param lst
in
remove_elements {n} (x, lst)
end
fn {a : vt@ype}
remove_dups
{n : int}
(lst : &list_vt (a, n) >> list_vt (a, m))
:<!wrt> #[m : nat | m <= n]
void =
let
fun
rmv_dups {n : nat}
.<n>.
(lst : &list_vt (a, n) >> list_vt (a, m))
:<!wrt> #[m : nat | m <= n]
void =
case+ lst of
| NIL => ()
| head :: NIL => ()
| @ head :: tail =>
let
val () = remove_equal_elements (head, tail)
val () = rmv_dups tail
prval () = fold@ lst
in
end
prval () = lemma_list_vt_param lst
in
rmv_dups {n} lst
end
implement {a}
list_vt_remove_dups {n} lst =
let
var lst = lst
in
remove_dups {n} lst;
lst
end
(*------------------------------------------------------------------*)
implement
remove_dups$eq<Strptr1> (s, t) =
($UN.strptr2string s = $UN.strptr2string t)
implement
remove_dups$clear<Strptr1> s =
strptr_free s
implement
array_uninitize$clear<Strptr1> (i, s) =
strptr_free s
implement
fprint_ref<Strptr1> (outf, s) =
fprint! (outf, $UN.strptr2string s)
implement (* A demonstration with linear strings. *)
main0 () =
let
#define N 10
val data =
$list_vt{Strptr1}
(string0_copy "a", string0_copy "c", string0_copy "b",
string0_copy "e", string0_copy "a", string0_copy "a",
string0_copy "d", string0_copy "d", string0_copy "b",
string0_copy "c")
var arr : @[Strptr1][N]
val () = array_copy_from_list_vt<Strptr1> (arr, data)
prval pf_arr = view@ arr
val p_arr = addr@ arr
val [m : int]
@(pf_uniq, pf_abandoned | m) =
array_remove_dups<Strptr1> (pf_arr | p_arr, i2sz N)
val () = fprint_array_sep<Strptr1> (stdout_ref, !p_arr, m, " ")
val () = println! ()
val () = array_uninitize<Strptr1> (!p_arr, m)
prval () = view@ arr :=
array_v_unsplit (pf_uniq, pf_abandoned)
in
end
(*------------------------------------------------------------------*)
</syntaxhighlight>
{{out}}
<pre> a c b e d</pre>
=== ATS2 implementation for values having both ''order'' and ''equality'' predicates ===
Sort the elements and then keep only the first element of each run of equal elements.
This method is limited in speed by the speed of the sorting algorithm. That can vary greatly according to algorithm and circumstances, but typically is much better than O(n*n). Below (simply because it is convenient) I use the quicksort that is in the ATS2 prelude.
<syntaxhighlight lang="ats">
(* Remove duplicate elements.
The elements are sorted and then only unique values are kept. *)
#include "share/atspre_staload.hats"
(* How the remove_dups template function will be called. *)
extern fn {a : t@ype}
remove_dups
{n : int}
(lt : (a, a) -<cloref> bool, (* "less than" *)
eq : (a, a) -<cloref> bool, (* "equals" *)
src : arrayref (a, n),
n : size_t n,
dst : arrayref (a, n),
m : &size_t? >> size_t m)
: #[m : nat | m <= n]
void
implement {a}
remove_dups {n} (lt, eq, src, n, dst, m) =
if n = i2sz 0 then
m := i2sz 0
else
let
prval () = lemma_arrayref_param src (* Prove 0 <= n. *)
(* Sort a copy of src. *)
val arr = arrayptr_refize (arrayref_copy (src, n))
implement array_quicksort$cmp<a> (x, y) =
if x \lt y then ~1 else 1
val () = arrayref_quicksort<a> (arr, n)
(* Copy only the first element of each run of equal elements. *)
val () = dst[0] := arr[0]
fun
loop {i : int | 1 <= i; i <= n}
{j : int | 1 <= j; j <= i}
.<n - i>.
(i : size_t i,
j : size_t j)
: [m : int | 1 <= m; m <= n]
size_t m =
if i = n then
j
else if arr[pred i] \eq arr[i] then
loop (succ i, j)
else
begin
dst[j] := arr[i];
loop (succ i, succ j)
end
val () = m := loop (i2sz 1, i2sz 1)
in
end
implement (* A demonstration. *)
main0 () =
let
val src =
arrayref_make_list<string>
(10, $list ("a", "c", "b", "e", "a",
"a", "d", "d", "b", "c"))
val dst = arrayref_make_elt<string> (i2sz 10, "?")
var m : size_t
in
remove_dups<string> (lam (x, y) => x < y,
lam (x, y) => x = y,
src, i2sz 10, dst, m);
let
prval [m : int] EQINT () = eqint_make_guint m
var i : natLte m
in
for (i := 0; i2sz i <> m; i := succ i)
print! (" ", dst[i]);
println! ()
end
end
</syntaxhighlight>
{{out}}
<pre> a b c d e</pre>
=== ATS2 implementation using a radix sort ===
This method runs in O(nw) time, where n is the number of elements n and w is a factor that is constant for elements that are fixed-size integers.
The implementation is for unsigned integers and puts the unique numbers into a second array in ascending order.
Radix sorting can sort an array of elements only into the encoding order of their keys, but that is a common case. Here the only reason to sort at all is to quickly eliminate duplicates.
<syntaxhighlight lang="ats">
(* Remove duplicate elements.
The best sorting algorithms, it is said, are O(n log n) and require
an order predicate.
But this is true only for a general sorting routine. A radix sort
for fixed-size integers is O(n), and requires no order predicate.
Here I use such a radix sort. *)
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
(* How the remove_dups template function will be called. *)
extern fn {tk : tkind}
remove_dups
{n : int}
(src : arrayref (g0uint tk, n),
n : size_t n,
dst : arrayref (g0uint tk, n),
m : &size_t? >> size_t m)
: #[m : nat | m <= n]
void
(*------------------------------------------------------------------*)
(* A radix sort for unsigned integers, copied from my contribution to
the radix sort task. *)
extern fn {a : vt@ype}
{tk : tkind}
g0uint_radix_sort
{n : int}
(arr : &array (a, n) >> _,
n : size_t n)
:<!wrt> void
extern fn {a : vt@ype}
{tk : tkind}
g0uint_radix_sort$key
{n : int}
{i : nat | i < n}
(arr : &RD(array (a, n)),
i : size_t i)
:<> g0uint tk
fn {}
bin_sizes_to_indices
(bin_indices : &array (size_t, 256) >> _)
:<!wrt> void =
let
fun
loop {i : int | i <= 256}
{accum : int}
.<256 - i>.
(bin_indices : &array (size_t, 256) >> _,
i : size_t i,
accum : size_t accum)
:<!wrt> void =
if i <> i2sz 256 then
let
prval () = lemma_g1uint_param i
val elem = bin_indices[i]
in
if elem = i2sz 0 then
loop (bin_indices, succ i, accum)
else
begin
bin_indices[i] := accum;
loop (bin_indices, succ i, accum + g1ofg0 elem)
end
end
in
loop (bin_indices, i2sz 0, i2sz 0)
end
fn {a : vt@ype}
{tk : tkind}
count_entries
{n : int}
{shift : nat}
(arr : &RD(array (a, n)),
n : size_t n,
bin_indices : &array (size_t?, 256)
>> array (size_t, 256),
all_expended : &bool? >> bool,
shift : int shift)
:<!wrt> void =
let
fun
loop {i : int | i <= n}
.<n - i>.
(arr : &RD(array (a, n)),
bin_indices : &array (size_t, 256) >> _,
all_expended : &bool >> bool,
i : size_t i)
:<!wrt> void =
if i <> n then
let
prval () = lemma_g1uint_param i
val key : g0uint tk = g0uint_radix_sort$key<a><tk> (arr, i)
val key_shifted = key >> shift
val digit = ($UN.cast{uint} key_shifted) land 255U
val [digit : int] digit = g1ofg0 digit
extern praxi set_range :
() -<prf> [0 <= digit; digit <= 255] void
prval () = set_range ()
val count = bin_indices[digit]
val () = bin_indices[digit] := succ count
in
all_expended := all_expended * iseqz key_shifted;
loop (arr, bin_indices, all_expended, succ i)
end
prval () = lemma_array_param arr
in
array_initize_elt<size_t> (bin_indices, i2sz 256, i2sz 0);
all_expended := true;
loop (arr, bin_indices, all_expended, i2sz 0)
end
fn {a : vt@ype}
{tk : tkind}
sort_by_digit
{n : int}
{shift : nat}
(arr1 : &RD(array (a, n)),
arr2 : &array (a, n) >> _,
n : size_t n,
all_expended : &bool? >> bool,
shift : int shift)
:<!wrt> void =
let
var bin_indices : array (size_t, 256)
in
count_entries<a><tk> (arr1, n, bin_indices, all_expended, shift);
if all_expended then
()
else
let
fun
rearrange {i : int | i <= n}
.<n - i>.
(arr1 : &RD(array (a, n)),
arr2 : &array (a, n) >> _,
bin_indices : &array (size_t, 256) >> _,
i : size_t i)
:<!wrt> void =
if i <> n then
let
prval () = lemma_g1uint_param i
val key = g0uint_radix_sort$key<a><tk> (arr1, i)
val key_shifted = key >> shift
val digit = ($UN.cast{uint} key_shifted) land 255U
val [digit : int] digit = g1ofg0 digit
extern praxi set_range :
() -<prf> [0 <= digit; digit <= 255] void
prval () = set_range ()
val [j : int] j = g1ofg0 bin_indices[digit]
(* One might wish to get rid of this assertion somehow,
to eliminate the branch, should it prove a
problem. *)
val () = $effmask_exn assertloc (j < n)
val p_dst = ptr_add<a> (addr@ arr2, j)
and p_src = ptr_add<a> (addr@ arr1, i)
val _ = $extfcall (ptr, "memcpy", p_dst, p_src,
sizeof<a>)
val () = bin_indices[digit] := succ (g0ofg1 j)
in
rearrange (arr1, arr2, bin_indices, succ i)
end
prval () = lemma_array_param arr1
in
bin_sizes_to_indices<> bin_indices;
rearrange (arr1, arr2, bin_indices, i2sz 0)
end
end
fn {a : vt@ype}
{tk : tkind}
g0uint_sort {n : pos}
(arr1 : &array (a, n) >> _,
arr2 : &array (a, n) >> _,
n : size_t n)
:<!wrt> void =
let
fun
loop {idigit_max, idigit : nat | idigit <= idigit_max}
.<idigit_max - idigit>.
(arr1 : &array (a, n) >> _,
arr2 : &array (a, n) >> _,
from1to2 : bool,
idigit_max : int idigit_max,
idigit : int idigit)
:<!wrt> void =
if idigit = idigit_max then
begin
if ~from1to2 then
let
val _ =
$extfcall (ptr, "memcpy", addr@ arr1, addr@ arr2,
sizeof<a> * n)
in
end
end
else if from1to2 then
let
var all_expended : bool
in
sort_by_digit<a><tk> (arr1, arr2, n, all_expended,
8 * idigit);
if all_expended then
()
else
loop (arr1, arr2, false, idigit_max, succ idigit)
end
else
let
var all_expended : bool
in
sort_by_digit<a><tk> (arr2, arr1, n, all_expended,
8 * idigit);
if all_expended then
let
val _ =
$extfcall (ptr, "memcpy", addr@ arr1, addr@ arr2,
sizeof<a> * n)
in
end
else
loop (arr1, arr2, true, idigit_max, succ idigit)
end
in
loop (arr1, arr2, true, sz2i sizeof<g1uint tk>, 0)
end
#define SIZE_THRESHOLD 256
extern praxi
unsafe_cast_array
{a : vt@ype}
{b : vt@ype}
{n : int}
(arr : &array (b, n) >> array (a, n))
:<prf> void
implement {a} {tk}
g0uint_radix_sort {n} (arr, n) =
if n <> 0 then
let
prval () = lemma_array_param arr
fn
sort {n : pos}
(arr1 : &array (a, n) >> _,
arr2 : &array (a, n) >> _,
n : size_t n)
:<!wrt> void =
g0uint_sort<a><tk> (arr1, arr2, n)
in
if n <= SIZE_THRESHOLD then
let
var arr2 : array (a, SIZE_THRESHOLD)
prval @(pf_left, pf_right) =
array_v_split {a?} {..} {SIZE_THRESHOLD} {n} (view@ arr2)
prval () = view@ arr2 := pf_left
prval () = unsafe_cast_array{a} arr2
val () = sort (arr, arr2, n)
prval () = unsafe_cast_array{a?} arr2
prval () = view@ arr2 :=
array_v_unsplit (view@ arr2, pf_right)
in
end
else
let
val @(pf_arr2, pfgc_arr2 | p_arr2) = array_ptr_alloc<a> n
macdef arr2 = !p_arr2
prval () = unsafe_cast_array{a} arr2
val () = sort (arr, arr2, n)
prval () = unsafe_cast_array{a?} arr2
val () = array_ptr_free (pf_arr2, pfgc_arr2 | p_arr2)
in
end
end
(*------------------------------------------------------------------*)
(* An implementation of the remove_dups template function, which also
sorts the elements. *)
implement {tk}
remove_dups {n} (src, n, dst, m) =
if n = i2sz 0 then
m := i2sz 0
else
let
prval () = lemma_arrayref_param src (* Prove 0 <= n. *)
(* Sort a copy of src. *)
val arrptr = arrayref_copy (src, n)
val @(pf_arr | p_arr) = arrayptr_takeout_viewptr arrptr
val () = g0uint_radix_sort<g0uint tk><tk> (!p_arr, n)
prval () = arrayptr_addback (pf_arr | arrptr)
(* Copy only the first element of each run of equals. *)
val () = dst[0] := arrptr[0]
fun
loop {i : int | 1 <= i; i <= n}
{j : int | 1 <= j; j <= i}
.<n - i>.
(arrptr : !arrayptr (g0uint tk, n),
i : size_t i,
j : size_t j)
: [m : int | 1 <= m; m <= n]
size_t m =
if i = n then
j
else if arrptr[pred i] = arrptr[i] then
loop (arrptr, succ i, j)
else
begin
dst[j] := arrptr[i];
loop (arrptr, succ i, succ j)
end
val () = m := loop (arrptr, i2sz 1, i2sz 1)
val () = arrayptr_free arrptr
in
end
(*------------------------------------------------------------------*)
(* A demonstration. *)
implement
main0 () =
let
implement
g0uint_radix_sort$key<uint><uintknd> (arr, i) =
arr[i]
val src =
arrayref_make_list<uint>
(10, $list (1U, 3U, 2U, 5U, 1U, 1U, 4U, 4U, 2U, 3U))
val dst = arrayref_make_elt<uint> (i2sz 10, 123456789U)
var m : size_t
in
remove_dups<uintknd> (src, i2sz 10, dst, m);
let
prval [m : int] EQINT () = eqint_make_guint m
var i : natLte m
in
for (i := 0; i2sz i <> m; i := succ i)
print! (" ", dst[i]);
println! ()
end
end
(*------------------------------------------------------------------*)
</syntaxhighlight>
{{out}}
<pre> 1 2 3 4 5</pre>
=== ATS2 implementation using a hash table ===
The speed of this method depends on the speed of the hash table.
<syntaxhighlight lang="ats">
(* Remove duplicate elements.
Elements already seen are put into a hash table. *)
#include "share/atspre_staload.hats"
(* Use hash tables from the libats/ML library. *)
staload "libats/ML/SATS/hashtblref.sats"
staload _ = "libats/ML/DATS/hashtblref.dats"
staload _ = "libats/DATS/hashfun.dats"
staload _ = "libats/DATS/hashtbl_chain.dats"
staload _ = "libats/DATS/linmap_list.dats"
(* How the remove_dups template function will be called. *)
extern fn {key, a : t@ype}
remove_dups
{n : int}
(key : a -<cloref> key,
src : arrayref (a, n),
n : size_t n,
dst : arrayref (a, n),
m : &size_t? >> size_t m)
: #[m : nat | m <= n]
void
implement {key, a}
remove_dups {n} (key, src, n, dst, m) =
if n = i2sz 0 then
m := i2sz 0
else
let
prval () = lemma_arrayref_param src (* Prove 0 <= n. *)
fun
loop {i : nat | i <= n}
{j : nat | j <= i}
.<n - i>.
(ht : hashtbl (key, a),
i : size_t i,
j : size_t j)
: [m : nat | m <= n]
size_t m =
if i = n then
j
else
let
val x = src[i]
val k = key x
in
case+ hashtbl_search<key, a> (ht, k) of
| ~ None_vt () =>
begin (* An element not yet encountered. Copy it. *)
hashtbl_insert_any<key, a> (ht, k, x);
dst[j] := x;
loop (ht, succ i, succ j)
end
| ~ Some_vt _ =>
begin (* An element already encountered. Skip it. *)
loop (ht, succ i, j)
end
end;
in
m := loop (hashtbl_make_nil<key, a> (i2sz 1024),
i2sz 0, i2sz 0)
end
implement (* A demonstration. *)
main0 () =
let
val src =
arrayref_make_list<string>
(10, $list ("a", "c", "b", "e", "a",
"a", "d", "d", "b", "c"))
val dst = arrayref_make_elt<string> (i2sz 10, "?")
var m : size_t
in
remove_dups<string, string> (lam s => s, src, i2sz 10, dst, m);
let
prval [m : int] EQINT () = eqint_make_guint m
var i : natLte m
in
for (i := 0; i2sz i <> m; i := succ i)
print! (" ", dst[i]);
println! ()
end
end
</syntaxhighlight>
{{out}}
<pre> a c b e d</pre>
=== ATS2 implementation for values containing a mutable ''seen'' flag ===
This method runs O(n) in the number of elements. It can be useful when you are working with references to complicated data structures. It works only if the array contains references to structures, rather than the structures themselves.
This implementation is for non-linear types only and happens to demonstrate "ordinary" imperative programming in ATS2: without dependent types, proofs, etc. The code is still safe against over-running array boundaries, but the safety is enforced by run-time checks rather than proofs.
<syntaxhighlight lang="ats">
(* Remove duplicate elements.
This implementation is for elements that contain a "this has been
seen" flag. It is O(n) in the number of elements.
Also, this implementation demonstrates that imperative programming,
without dependent types or proofs, is possible in ATS. *)
#include "share/atspre_staload.hats"
(* A tuple in the heap. *)
typedef seen_or_not (a : t@ype+) = '(a, ref bool)
(* How the remove_dups function will be called. *)
extern fn {a : t@ype}
remove_dups
(given_data : arrszref (seen_or_not a),
space_for_result : arrszref (seen_or_not a),
num_of_unique_elems : &size_t? >> size_t)
: void
implement {a}
remove_dups (given_data, space_for_result, num_of_unique_elems) =
let
macdef seen (i) = given_data[,(i)].1
var i : size_t
var j : size_t
in
(* Clear all the "seen" flags. *)
for (i := i2sz 0; i <> size given_data; i := succ i)
!(seen i) := false;
(* Loop through given_data, copying (pointers to) any values that
have not yet been seen. *)
j := i2sz 0;
for (i := i2sz 0; i <> size given_data; i := succ i)
if !(seen i) then
() (* Skip any element that has already been seen. *)
else
begin
!(seen i) := true; (* Mark the element as seen. *)
space_for_result[j] := given_data[i];
j := succ j
end;
num_of_unique_elems := j
end
implement (* A demonstration. *)
main0 () =
let
(* Define some values. *)
val a = '("a", ref<bool> false)
val b = '("b", ref<bool> false)
val c = '("c", ref<bool> false)
val d = '("d", ref<bool> false)
val e = '("e", ref<bool> false)
(* Fill an array with values. *)
val data =
arrszref_make_list ($list (a, c, b, e, a, a, d, d, b, c))
(* Allocate storage for the result. *)
val unique_elems = arrszref_make_elt (i2sz 10, a)
var num_of_unique_elems : size_t
var i : size_t
in
(* Remove duplicates. *)
remove_dups<string> (data, unique_elems, num_of_unique_elems);
(* Print the results. *)
for (i := i2sz 0; i <> num_of_unique_elems; i := succ i)
print! (" ", unique_elems[i].0);
println! ()
end
</syntaxhighlight>
{{out}}
<pre> a c b e d</pre>
=={{header|AutoHotkey}}==
Built in Sort has an option to remove duplicates
<syntaxhighlight lang="autohotkey">a = 1,2,1,4,5,2,15,1,3,4
Sort, a, a, NUD`,
MsgBox % a ; 1,2,3,4,5,15</syntaxhighlight>
=={{header|AWK}}==
We produce an array a with duplicates from a string;
then index a second array b with the contents of a,
so that duplicates make only one entry;
then produce a string with the keys of b,
which is finally output.
<syntaxhighlight lang="awk">$ awk 'BEGIN{split("a b c d c b a",a);for(i in a)b[a[i]]=1;r="";for(i in b)r=r" "i;print r}'
a b c d</syntaxhighlight>
=={{header|BASIC}}==
==={{header|ANSI BASIC}}===
{{trans|Modula-2}}
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">
100 REM Remove duplicate elements
110 DIM DataArray(1 TO 7), ResultArray(1 TO 7)
120 ! Set the data.
130 FOR I = 1 TO 7
140 READ DataArray(I)
150 NEXT I
160 ! Remove duplicates
170 LET ResultArray(1) = DataArray(1)
180 LET LastResultIndex = 1
190 LET Position = 1
200 DO WHILE Position < UBOUND(DataArray)
210 LET Position = Position + 1
220 LET IsNewNumber = -1
230 FOR ResultIndex = 1 TO LastResultIndex
240 IF DataArray(Position) = ResultArray(ResultIndex) THEN
250 LET IsNewNumber = 0
260 EXIT FOR
270 END IF
280 NEXT ResultIndex
290 IF IsNewNumber = -1 THEN
300 LET LastResultIndex = LastResultIndex + 1
310 LET ResultArray(LastResultIndex) = DataArray(Position)
320 END IF
330 LOOP
340 FOR ResultIndex = 1 TO LastResultIndex
350 PRINT ResultArray(ResultIndex)
360 NEXT ResultIndex
370 DATA 1, 2, 2, 3, 4, 5, 5
380 END
</syntaxhighlight>
{{out}}
<pre>
1
2
3
4
5
</pre>
==={{header|Applesoft BASIC}}===
<syntaxhighlight lang="basic">100 DIM L$(15)
110 L$(0) = "NOW"
Line 541 ⟶ 1,578:
540 RETURN</syntaxhighlight>
==={{header|
{{trans|True BASIC}}
<syntaxhighlight lang="basic256">
Line 600 ⟶ 1,611:
</syntaxhighlight>
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<syntaxhighlight lang="bbcbasic"> DIM list$(15)
Line 628 ⟶ 1,638:
Now is the time for all good men to come aid of party.
</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
Sub removeDuplicates(a() As Integer, b() As Integer)
Dim lb As Integer = LBound(a)
Dim ub As Integer = UBound(a)
If ub = -1 Then Return '' empty array
Redim b(lb To ub)
b(lb) = a(lb)
Dim count As Integer = 1
Dim unique As Boolean
For i As Integer = lb + 1 To ub
unique = True
For j As Integer = lb to i - 1
If a(i) = a(j) Then
unique = False
Exit For
End If
Next j
If unique Then
b(lb + count) = a(i)
count += 1
End If
Next i
If count > 0 Then Redim Preserve b(lb To lb + count - 1)
End Sub
Dim a(1 To 10) As Integer = {1, 2, 1, 4, 5, 2, 15, 1, 3, 4}
Dim b() As Integer
removeDuplicates a(), b()
For i As Integer = LBound(b) To UBound(b)
Print b(i); " ";
Next
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
{{out}}
<pre>
1 2 4 5 15 3
</pre>
==={{header|FutureBasic}}===
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
CFArrayRef array, unique
OrderedSetRef ordered
array = @[@"A", @"B", @"C", @"B", @"A", @"C", @"A", @"C", @"A", @"B", @"C"]
ordered = fn OrderedSetWithArray( array )
NSLog( @"%@", fn OrderedSetArray( ordered ) )
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
(
A,
B,
C
)
</pre>
==={{header|Gambas}}===
'''[https://gambas-playground.proko.eu/?gist=1e2bb524d2278cd88bccdc21a1683296 Click this link to run this code]'''
<syntaxhighlight lang="gambas">Public Sub Main()
Dim sString As String[] = Split("Now is the time for all the good men to come to the aid of the good party 1 2 1 3 3 3 2 1 1 2 3 4 33 2 5 4 333 5", " ")
Dim sFix As New String[]
Dim sTemp As String
For Each sTemp In sString
sTemp &= " "
If InStr(sFix.Join(" ") & " ", sTemp) Then Continue
sFix.Add(Trim(sTemp))
Next
Print sFix.Join(" ")
End</syntaxhighlight>
Output:
<pre>
Now is the time for all good men to come aid of party 1 2 3 4 33 5 333
</pre>
==={{header|GW-BASIC}}===
{{trans|Modula-2}}
{{works with|BASICA}}
{{works with|PC-BASIC|any}}
<syntaxhighlight lang="qbasic">
10 ' Remove Duplicates
20 OPTION BASE 1
30 LET MAXI% = 7
40 DIM D(7), R(7): ' data, result
50 ' Set the data.
60 FOR I% = 1 TO 7
70 READ D(I%)
80 NEXT I%
90 ' Remove duplicates.
100 LET R(1) = D(1)
110 LET LRI% = 1: ' last index of result
120 LET P% = 1: ' position
130 WHILE P% < MAXI%
140 LET P% = P% + 1
150 LET ISNEW = 1: ' is a new number?
160 LET RI% = 1: ' current index of result
170 WHILE (RI% <= LRI%) AND ISNEW
180 IF D(P%) = R(RI%) THEN LET ISNEW = 0
190 LET RI% = RI% + 1
200 WEND
210 IF ISNEW THEN LET LRI% = LRI% + 1: LET R(LRI%) = D(P%)
220 WEND
230 FOR RI% = 1 TO LRI%
240 PRINT R(RI%)
250 NEXT RI%
260 END
1000 DATA 1, 2, 2, 3, 4, 5, 5
</syntaxhighlight>
{{out}}
<pre>
1
2
3
4
5
</pre>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">100 PROGRAM "RemoveDu.bas"
110 RANDOMIZE
120 NUMERIC ARR(1 TO 20),TOP
130 LET TOP=FILL(ARR)
140 CALL WRITE(ARR,TOP)
150 LET TOP=REMOVE(ARR)
160 CALL WRITE(ARR,TOP)
170 DEF WRITE(REF A,N)
180 FOR I=1 TO N
190 PRINT A(I);
200 NEXT
210 PRINT
220 END DEF
230 DEF FILL(REF A)
240 LET FILL=UBOUND(A):LET A(LBOUND(A))=1
250 FOR I=LBOUND(A)+1 TO UBOUND(A)
260 LET A(I)=A(I-1)+RND(3)
270 NEXT
280 END DEF
290 DEF REMOVE(REF A)
300 LET ST=0
310 FOR I=LBOUND(A)+1 TO UBOUND(A)
320 IF A(I-1)=A(I) THEN LET ST=ST+1
330 IF ST>0 THEN LET A(I-ST)=A(I)
340 NEXT
350 LET REMOVE=UBOUND(A)-ST
360 END DEF</syntaxhighlight>
{{out}}
<pre>START
1 1 2 4 5 7 9 10 12 14 16 16 16 17 18 20 20 22 23 23
1 2 4 5 7 9 10 12 14 16 17 18 20 22 23
ok
START
1 2 4 5 5 5 7 8 9 9 10 10 10 12 14 15 17 17 18 20
1 2 4 5 7 8 9 10 12 14 15 17 18 20
ok
START
1 3 3 4 5 6 8 10 11 12 14 16 16 16 16 18 18 19 21 21
1 3 4 5 6 8 10 11 12 14 16 18 19 21
ok
START
1 3 3 4 5 5 7 9 11 13 13 14 16 17 17 18 19 19 20 21
1 3 4 5 7 9 11 13 14 16 17 18 19 20 21
ok
START
1 2 3 5 5 6 6 7 8 10 12 14 15 17 17 19 21 23 25 25
1 2 3 5 6 7 8 10 12 14 15 17 19 21 23 25
ok</pre>
==={{header|Liberty BASIC}}===
LB has arrays, but here the elements are stored in a space-separated string.
{{works sith|Just BASIC}}
<syntaxhighlight lang="lb">
a$ =" 1 $23.19 2 elbow 3 2 Bork 4 3 elbow 2 $23.19 "
print "Original set of elements = ["; a$; "]"
b$ =removeDuplicates$( a$)
print "With duplicates removed = ["; b$; "]"
end
function removeDuplicates$( in$)
o$ =" "
i =1
do
term$ =word$( in$, i, " ")
if instr( o$, " "; term$; " ") =0 and term$ <>" " then o$ =o$ +term$ +" "
i =i +1
loop until term$ =""
removeDuplicates$ =o$
end function
</syntaxhighlight>
{{out}}
<pre>
Original set of elements = [ 1 $23.19 2 elbow 3 2 Bork 4 3 elbow 2 $23.19 ]
With duplicates removed = [ 1 $23.19 2 elbow 3 Bork 4 ]
</pre>
==={{header|Microsoft Small Basic}}===
{{trans|Modula-2}}
<syntaxhighlight lang="microsoftsmallbasic">
' Set the data.
dataArray[1] = 1
dataArray[2] = 2
dataArray[3] = 2
dataArray[4] = 3
dataArray[5] = 4
dataArray[6] = 5
dataArray[7] = 5
resultArray[1] = dataArray[1]
lastResultIndex = 1
position = 1
While position < Array.GetItemCount(dataArray)
position = position + 1
isNewNumber = 1 ' logical 1
resultIndex = 1
While (resultIndex <= lastResultIndex) And isNewNumber = 1
If dataArray[position] = resultArray[resultIndex] Then
isNewNumber = 0
EndIf
resultIndex = resultIndex + 1
EndWhile
If isNewNumber = 1 Then
lastResultIndex = lastResultIndex + 1
resultArray[lastResultIndex] = dataArray[position]
EndIf
EndWhile
For resultIndex = 1 To lastResultIndex
TextWindow.WriteLine(resultArray[resultIndex])
EndFor
</syntaxhighlight>
==={{header|PureBasic}}===
Task solved with the built in Hash Table which are called Maps in PureBasic
<syntaxhighlight lang="purebasic">NewMap MyElements.s()
For i=0 To 9 ;Mark 10 items at random, causing high risk of duplication items.
x=Random(9)
t$="Number "+str(x)+" is marked"
MyElements(str(x))=t$ ; Add element 'X' to the hash list or overwrite if already included.
Next
ForEach MyElements()
Debug MyElements()
Next</syntaxhighlight>
Output may look like this, e.g. duplicated items are automatically removed as they have the same hash value.
Number 0 is marked
Number 2 is marked
Number 5 is marked
Number 6 is marked
==={{header|Run BASIC}}===
<syntaxhighlight lang="runbasic">a$ = "2 3 5 7 11 13 17 19 cats 222 -100.2 +11 1.1 +7 7. 7 5 5 3 2 0 4.4 2"
for i = 1 to len(a$)
a1$ = word$(a$,i)
if a1$ = "" then exit for
for i1 = 1 to len(b$)
if a1$ = word$(b$,i1) then [nextWord]
next i1
b$ = b$ + a1$ + " "
[nextWord]
next i
print "Dups:";a$
print "No Dups:";b$</syntaxhighlight>
<pre>Dups:2 3 5 7 11 13 17 19 cats 222 -100.2 +11 1.1 +7 7. 7 5 5 3 2 0 4.4 2
No Dups:2 3 5 7 11 13 17 19 cats 222 -100.2 +11 1.1 +7 7. 0 4.4 </pre>
==={{header|True BASIC}}===
{{trans|GW-BASIC}}
{{works with|QBasic}}
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">
OPTION BASE 1
LET max = 10
DIM dat(10), res(10)
FOR i = 1 TO max
READ dat(i)
NEXT i
DATA 1, 2, 1, 4, 5, 2, 15, 1, 3, 4
LET res(1) = dat(1)
LET count = 1
LET posic = 1
DO WHILE posic < max
LET posic = posic + 1
LET esnuevo = 1
LET indice = 1
DO WHILE (indice <= count) AND esnuevo = 1
IF dat(posic) = res(indice) THEN LET esnuevo = 0
LET indice = indice + 1
LOOP
IF esnuevo = 1 THEN
LET count = count + 1
LET res(count) = dat(posic)
END IF
LOOP
FOR i = 1 TO count
PRINT res(i);
NEXT i
END
</syntaxhighlight>
==={{header|VBA}}===
Hash Table Approach
Input list (variant : Long, Double, Boolean and Strings) :
Array(1.23456789101112E+16, True, False, True, "Alpha", 1, 235, 4, 1.25, 1.25, "Beta", 1.23456789101112E+16, "Delta", "Alpha", "Charlie", 1, 2, "Foxtrot", "Foxtrot", "Alpha", 235)
<syntaxhighlight lang="vb">
Option Explicit
Sub Main()
Dim myArr() As Variant, i As Long
myArr = Remove_Duplicate(Array(1.23456789101112E+16, True, False, True, "Alpha", 1, 235, 4, 1.25, 1.25, "Beta", 1.23456789101112E+16, "Delta", "Alpha", "Charlie", 1, 2, "Foxtrot", "Foxtrot", "Alpha", 235))
'return :
For i = LBound(myArr) To UBound(myArr)
Debug.Print myArr(i)
Next
End Sub
Private Function Remove_Duplicate(Arr As Variant) As Variant()
Dim myColl As New Collection, Temp() As Variant, i As Long, cpt As Long
ReDim Temp(UBound(Arr))
For i = LBound(Arr) To UBound(Arr)
On Error Resume Next
myColl.Add CStr(Arr(i)), CStr(Arr(i))
If Err.Number > 0 Then
On Error GoTo 0
Else
Temp(cpt) = Arr(i)
cpt = cpt + 1
End If
Next i
ReDim Preserve Temp(cpt - 1)
Remove_Duplicate = Temp
End Function</syntaxhighlight>
{{out}}
<pre> 1.23456789101112E+16
True
False
Alpha
1
235
4
1.25
Beta
Delta
Charlie
2
Foxtrot</pre>
==={{header|VBScript}}===
Hash Table Approach
<syntaxhighlight lang="vb">
Function remove_duplicates(list)
arr = Split(list,",")
Set dict = CreateObject("Scripting.Dictionary")
For i = 0 To UBound(arr)
If dict.Exists(arr(i)) = False Then
dict.Add arr(i),""
End If
Next
For Each key In dict.Keys
tmp = tmp & key & ","
Next
remove_duplicates = Left(tmp,Len(tmp)-1)
End Function
WScript.Echo remove_duplicates("a,a,b,b,c,d,e,d,f,f,f,g,h")
</syntaxhighlight>
{{Out}}
<pre>a,b,c,d,e,f,g,h</pre>
==={{header|Yabasic}}===
<syntaxhighlight lang="yabasic">data "Now", "is", "the", "time", "for", "all", "good", "men", "to", "come", "to", "the", "aid", "of", "the", "party.", ""
do
read p$
if p$ = "" break
if not instr(r$, p$) r$ = r$ + p$ + " "
loop
print r$</syntaxhighlight>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">⍷ 2‿4‿9‿7‿3‿7‿4‿1‿9‿2‿5‿7‿2‿2‿8‿9‿6‿6‿5‿8</syntaxhighlight>
{{out}}
<pre>⟨ 2 4 9 7 3 1 5 8 6 ⟩</pre>
=={{header|Bracmat}}==
Line 1,140 ⟶ 2,554:
<syntaxhighlight lang="e">[1,2,3,2,3,4].asSet().getElements()</syntaxhighlight>
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
a[] = [ 1 2 1 4 5 2 15 1 3 4 ]
for a in a[]
found = 0
for b in b[]
if a = b
found = 1
break 1
.
.
if found = 0
b[] &= a
.
.
print b[]
</syntaxhighlight>
=={{header|ECL}}==
Line 1,158 ⟶ 2,592:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import extensions;
import system'collections;
Line 1,168 ⟶ 2,602:
auto unique := new Map<int, int>();
nums.forEach::(n){ unique[n] := n };
console.printLine(unique.MapValues.asEnumerable())
Line 1,175 ⟶ 2,609:
<pre>
1,2,3,4
</pre>
=={{header|Ecstasy}}==
<syntaxhighlight lang="java">
module RetainUniqueValues {
void run() {
Int[] array = [1, 2, 3, 2, 1, 2, 3, 4, 5, 3, 2, 1];
array = array.distinct().toArray();
@Inject Console console;
console.print($"result={array}");
}
}
</syntaxhighlight>
{{out}}
<pre>
result=[1, 2, 3, 4, 5]
</pre>
Line 1,381 ⟶ 2,833:
<pre>Unique list has 6 elements: 1 2 3 4 5 6</pre>
=={{header|Frink}}==
Line 1,445 ⟶ 2,852:
[1, 2, 5, 6, 8, 9]
[9, 8, 6, 5, 2, 1]
</pre>
Line 1,728 ⟶ 3,086:
Original List, filtered: [1, 2, 3, a, b, c, 4, d]
Set: [1, 2, 3, a, b, c, 4, d]</pre>
=={{header|Haskell}}==
===Usage===
<syntaxhighlight lang="haskell"> print $ unique [4, 5, 4, 2, 3, 3, 4]
Line 1,867 ⟶ 3,182:
decide on result.</syntaxhighlight>
=={{header|J}}==
Line 1,936 ⟶ 3,201:
0 1 2
0 2 4</syntaxhighlight>
=={{header|Jakt}}==
The array version preserves order based on first occurrence.
<syntaxhighlight lang="jakt">
fn deduplicated<T>(anon array: [T]) throws -> [T] {
mut existing_items: {T} = {}
mut result: [T] = []
for value in array {
if not existing_items.contains(value) {
existing_items.add(value)
result.push(value)
}
}
return result
}
fn deduplicated_set<T>(anon array: [T]) throws -> {T} {
mut result: {T} = {}
for value in array {
result.add(value)
}
return result
}
fn main() {
let array = [1, 2, 3, 3, 2, 5, 4]
println("{}", deduplicated(array))
println("{}", deduplicated_set(array))
}
</syntaxhighlight>
=={{header|Java}}==
There is more than 1 way to achieve this. The most logical approach will depend on your application.<br />
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
</syntaxhighlight>
One way would be to add the values to a ''Set'' object, which only allows for unique values.
<syntaxhighlight lang="java">
int[] removeDuplicates(int[] values) {
/* use a LinkedHashSet to preserve order */
Set<Integer> set = new LinkedHashSet<>();
for (int value : values)
set.add(value);
values = new int[set.size()];
Iterator<Integer> iterator = set.iterator();
int index = 0;
while (iterator.hasNext())
values[index++] = iterator.next();
return values;
}
</syntaxhighlight>
Alternately, you could simply add the values to a mutable ''List'', checking if the list already contains the value before adding it.
<syntaxhighlight lang="java">
int[] removeDuplicates(int[] values) {
List<Integer> list = new ArrayList<>();
for (int value : values)
if (!list.contains(value)) list.add(value);
values = new int[list.size()];
int index = 0;
for (int value : list)
values[index++] = value;
return values;
}
</syntaxhighlight>
<pre>
[2, 1, 4, 1, 1, 3, 1, 3, 1, 4, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3]
[2, 1, 4, 3]
[2, 4, 1, 4, 1, 4, 3, 1, 1, 3, 4, 4, 4, 4, 2, 1, 1, 2, 3, 2]
[2, 4, 1, 3]
</pre>
<br />
Alternate approaches
{{works with|Java|1.5}}
<syntaxhighlight lang="java5">import java.util.*;
Line 2,084 ⟶ 3,426:
<pre>[[4, 3, 2, 8, 0, 1, 9, 5, 7, 6], "chtoni elmsyarp"]</pre>
=={{header|Joy}}==
<syntaxhighlight lang="joy">DEFINE uniq == [[]] [[in] [swap pop] [cons] ifte] primrec.</syntaxhighlight>
=={{header|jq}}==
Line 2,218 ⟶ 3,563:
// result: array(3, 4, 8, 1, 5, 6, 9)</syntaxhighlight>
=={{header|
<syntaxhighlight lang="scheme">
{def removedup
{def removedup.loop
{lambda {:a :b}
{if {A.empty? :a}
then :b
else {removedup.loop {A.rest :a}
{if {= {A.in? {A.first :a} :b} -1}
then {A.addlast! {A.first :a} :b}
else :b}}}}}
{lambda {:s}
{S.replace (\[|\]|,) by space in
{A.disp
{removedup.loop {A.new :s} {A.new}}}}}}
-> removedup
{removedup 1 2 3 a b c 2 3 4 b c d}
-> 1 2 3 a b c 4 d
</syntaxhighlight>
=={{header|Logo}}==
Line 2,280 ⟶ 3,621:
{{out}}
<pre>1 2 3 4 nan bird cat dog</pre>
=={{header|M2000 Interpreter}}==
Example of using a Stack object for two types, number (by default 1 is double type), and a list for fast search, append, delete. A stack object is a collection type, which we can use Push to add on top or use Data to append to bottom. A module call pass parameters to current stack, as a frame over, with the left item at the top of the stack.
<syntaxhighlight lang="m2000 interpreter">
Flush // current stack has no items
// Number pop a number from stack of values
// Letter pop a string from stack of values
Module TestList {
// current stack has a number, 101
// we can create a private stack
a=stack:=1, 1, "c", "d", 2, 2, 3, 3, 3, "a", "a", "b", "b"
// A list use key/values or key/Key as value. Keys can be number or strings
// Duplicate not allowed. Exist( list_type, key_to_exam) return true if key exist
// Lists are inventories types wich can't hold duplicates (error produce if append a duplicate)
// Lists have O(1) for insert, delete, search (using Hash Table)
b=list
stack a {
// replace current stack with a, old current stack kept
while not empty
if islet then // if is letter (string)
if not exist(b, stackitem$()) then Append b, letter$ else drop
else.if not exist(b, stackitem()) then
Append b, number
else
drop // drop the item
end if
end while
}
// now old current stack return as current stack
// we can sort the b list
Sort b
Print b // print the list, using right align on columns for numbers, left for strings.
Print Number=101 // true
}
TestList 101
</syntaxhighlight>
Actual spaces on the result line are according to column width. Here is just one space.
{{out}}
<pre> 1 2 3a b c d</pre>
=={{header|Maple}}==
Line 2,330 ⟶ 3,713:
if (id != i) do deleteItem uniques i
)</syntaxhighlight>
=={{header|MiniScript}}==
Line 2,626 ⟶ 3,974:
sort(items, system.cmp[int]) # O(n log n)
echo filterDup(items) # O(n)</syntaxhighlight>
=={{header|Oberon-2}}==
{{trans|Modula-2}}
<syntaxhighlight lang="oberon2">MODULE RD;
IMPORT Out;
TYPE
TArray = ARRAY 7 OF INTEGER;
VAR
DataArray,ResultArray:TArray;
ResultIndex,LastResultIndex,Position:LONGINT;
IsNewNumber:BOOLEAN;
PROCEDURE Init(VAR A:TArray);
BEGIN
A[0] := 1; A[1] := 2; A[2] := 2; A[3] := 3;
A[4] := 4; A[5] := 5; A[6] := 5;
END Init;
BEGIN
Init(DataArray);
ResultArray[0] := DataArray[0];
LastResultIndex := 0;
Position := 0;
WHILE Position < LEN(DataArray)-1 DO
INC(Position);
IsNewNumber := TRUE;
ResultIndex := 0;
WHILE(ResultIndex <= LastResultIndex) & (IsNewNumber) DO
IF DataArray[Position] = ResultArray[ResultIndex] THEN
IsNewNumber := FALSE;
END;
INC(ResultIndex);
END;
IF IsNewNumber THEN
INC(LastResultIndex);
ResultArray[LastResultIndex] := DataArray[Position];
END;
END;
FOR ResultIndex := 0 TO LastResultIndex DO
Out.Int(ResultArray[ResultIndex],0); Out.Char(' ');
END;
Out.Ln;
END RD.
</syntaxhighlight>
=={{header|Objeck}}==
Line 2,942 ⟶ 4,337:
<syntaxhighlight lang="prolog">?- distinct([A, A, 1, 2, 3, 2, 3, 4],Xs).
Xs = [A, 1, 2, 3, 4]</syntaxhighlight>
=={{header|Python}}==
Line 3,329 ⟶ 4,705:
<pre>
Now is the time for all good men to come aid of party.
</pre>
=={{header|RPL}}==
We follow here a fourth way, which requires few words and take advantage of the (relative) speed of the <code>POS</code> function.
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ → input
≪ { }
1 input SIZE '''FOR''' j
input j GET
'''IF''' DUP2 POS '''THEN''' DROP '''ELSE''' + '''END '''
'''NEXT'''
≫ ≫ ‘'''NODUP'''’ STO
|
'''NODUP''' ''( { a b a...c } -- { a b..c } ) ''
Initialize output list
Go through input list
If input[j] already in output list
then forget it else add it to output list
End loop
|}
{ 1 2 3 'a' 'b' 'c' 2 3 4 'b' 'c' 'd' } '''NODUP'''
{{out}}
<pre>
1: { 1 2 3 'a' 'b' 'c' 4 'd' }
</pre>
Line 3,379 ⟶ 4,785:
unique ["hi","hey","hello","hi","hey","heyo"] # => ["hi", "hey", "hello", "heyo"]
unique [1,2,3,4,1,2,3,5,1,2,3,4,5] # => [1,2,3,4,5]</syntaxhighlight>
=={{header|Rust}}==
Line 3,702 ⟶ 5,090:
With the correct option, the <code>lsort</code> command will remove duplicates.
<syntaxhighlight lang="tcl">set result [lsort -unique $listname]</syntaxhighlight>
=={{header|TSE SAL}}==
Line 3,877 ⟶ 5,228:
{{out}}
<pre>'mspi'</pre>
=={{header|Vedit macro language}}==
The input "array" is an edit buffer where each line is one element.
<syntaxhighlight lang="vedit">Sort(0, File_Size) // sort the data
Line 3,957 ⟶ 5,235:
=={{header|Vim Script}}==
<syntaxhighlight lang="vim">call filter(list, 'count(list, v:val) == 1')</syntaxhighlight>
Line 4,003 ⟶ 5,280:
</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">const list = 'a,1,a,b,b,c,d,e,d,0,f,f,5,f,g,h,1,3,3'
fn main() {
Line 4,043 ⟶ 5,320:
=={{header|Wren}}==
{{libheader|Wren-sort}}
<syntaxhighlight lang="
// Using a map - order of distinct items is undefined.
Line 4,148 ⟶ 5,425:
Pack myboxwithfvedznlqurjgs.
</pre>
=={{header|zkl}}==
| |||