Algebraic data types: Difference between revisions
→{{header|Phix}}
m (→{{header|REXX}}: added an output section.) |
|||
Line 1,079:
{{out}}
<pre>[B [B [B (Any) 1 [R (Any) 2 (Any)]] 3 [B (Any) 4 [R (Any) 5 (Any)]]] 6 [B [B (Any) 7 (Any)] 8 [B [R (Any) 9 (Any)] 10 (Any)]]]</pre>
=={{header|Phix}}==
There is no formal support for this sort of thing in Phix, but that's not to say that whipping
something up is likely to be particularly difficult, so let's give it a whirl.
Uses a slightly tweaked version of demo\rosetta\VisualiseTree.exw, for the full runnable code
see demo\rosetta\Pattern_matching.exw (shipped with 0.8.0+).
First, imagine the following is in say algebraic_data_types.e. It is not quite generic enough,
and there are too many little fudges, such as that "and not string(ki)", and the use of 0 for
the "any value", and {} to indicate failure, for it to end up in builtins\, but not exactly
difficult to copy/maintain on a per-project basis.
<lang Phix>function match_one(sequence key, object t)
sequence res = {}
if sequence(t)
and length(key)==length(t) then
for i=1 to length(key) do
object ki = key[i], ti = t[i]
if sequence(ki) and not string(ki) then
sequence r2 = match_one(ki,ti)
if r2={} then res = {} exit end if
res &= r2
else
if ki=0 then
res = append(res,ti)
else
if ki!=ti then res = {} exit end if
end if
end if
end for
end if
return res
end function
/*global*/ function match_algebraic(sequence set, t)
sequence s
for i=1 to length(set) do
s = match_one(set[i],t)
if length(s) then exit end if
end for
return s
end function</lang>
Then we can code something like this (with include algebraic_data_types.e)
<lang Phix>constant B = "B", R = "R"
function balance(sequence t)
sequence s = match_algebraic({{B,{R,{R,0,0,0},0,0},0,0},
{B,{R,0,0,{R,0,0,0}},0,0},
{B,0,0,{R,{R,0,0,0},0,0}},
{B,0,0,{R,0,0,{R,0,0,0}}}},t)
if length(s) then
object {a,x,b,y,c,z,d} = s
t = {R,{B,a,x,b},y,{B,c,z,d}}
end if
return t
end function
function ins(object tree, object leaf)
if tree=NULL then
tree = {R,NULL,leaf,NULL}
else
object {c,l,k,r} = tree
if leaf!=k then
if leaf<k then l = ins(l,leaf)
else r = ins(r,leaf)
end if
tree = balance({c,l,k,r})
end if
end if
return tree
end function
function tree_insert(object tree, object leaf)
tree = ins(tree,leaf)
tree[1] = B
return tree
end function
sequence stuff = shuffle(tagset(10))
object tree = NULL
for i=1 to length(stuff) do
tree = tree_insert(tree,stuff[i])
end for
visualise_tree(tree)</lang>
{{out}}
<pre>
┌R1
┌B2
┌B3
│└B4
─B5
│┌B6
││└R7
└B8
└B9
└R10
</pre>
=={{header|PicoLisp}}==
| |||