based on Okazaki's book

sml_style.rs

#![no_implicit_prelude]
#![allow(redundant_semicolons)]

extern crate core;
extern crate alloc;

use 
{ core::
  { option::Option::{*, self}
  , result::Result::{*, self}
  , clone::Clone
  , marker::PhantomData
  , ops::{Add, Deref}
  }
// , alloc::sync::{Arc, Weak}
, alloc::rc::{Rc, Weak}
};

type RcStrong<T> = Rc<T>;
type RcWeak<T>   = Weak<T>; 

#[derive(Debug)]
enum StackError 
{ /// an index error
  Subscript
}


// 2.1 Lists ////
trait STACK
{ type Struct<Item>
; fn empty    <I> () -> Self::Struct<I>
; fn is_empty <I> ( stack : &Self::Struct<I> ) -> bool
; fn cons     <I: Clone> 
                  ( head : &I, tail : &Self::Struct<I> ) -> Self::Struct<I>

; fn head     <I> ( stack : &Self::Struct<I> ) -> &I
  { &Self::head_tail(stack).expect("Stack should not be empty").0 }
  fn tail     <'a, I : 'a> ( stack : &'a Self::Struct<I> ) -> &'a Self::Struct<I>
  { &Self::head_tail(stack).expect("Stack should not be empty").1 }

  fn head_tail<I> ( stack : &Self::Struct<I> ) -> Option<(&I, &Self::Struct<I>)>
;
}
#[derive(Clone, PartialEq, Eq)]
enum List<I> 
{ Nil
, Cons(RcStrong<(I, List<I>)>) 
}


struct ListStack;
impl STACK for ListStack
{ type Struct<Item> = List<Item>
; fn empty<I>    () -> Self::Struct<I> { List::Nil }
  fn is_empty<I> ( stack : &Self::Struct<I> ) -> bool 
  { if let List::Nil = stack { true } 
    else {false} 
  }

  fn cons<I : Clone>     ( head : &I, tail : &Self::Struct<I> ) -> Self::Struct<I>
  { List::Cons(RcStrong::new((head.clone(), tail.clone()))) }

  fn head_tail<I>( stack : &Self::Struct<I> ) -> Option<(&I, &Self::Struct<I>)> 
  { match stack 
    { List::Nil => None
    , List::Cons(r) => Some((&r.0, &r.1))
    }
  }
}

struct DefaultStack<Module : STACK, Item>( PhantomData<Module::Struct<Item>> );

impl<M : STACK, I> DefaultStack<M, I>
where M::Struct<I> : Clone, I : Clone
{ fn reverse( stack : &M::Struct<I> ) -> M::Struct<I> 
  { Self::reverse_append(stack, &M::empty()) }
  

  fn reverse_append( stack_1 : &M::Struct<I>, stack_2 : &M::Struct<I> ) -> M::Struct<I>
  { let mut acc = stack_2.clone()
  ; let mut cur = stack_1
  ; loop { match M::head_tail( cur ) {
      None => return acc
    , Some((head, tail)) =>
      { ( acc , cur ) = ( M::cons(head, &acc), tail ) }
    }}
  }

  fn append( stack_1 : &M::Struct<I>, stack_2 : &M::Struct<I> ) -> M::Struct<I>
  { Self::reverse_append(&Self::reverse(stack_1), stack_2) }

  fn update( stack : &M::Struct<I>, index : usize, val : &I) -> M::Struct<I>
  { Self::try_update(stack, index, val).unwrap() }

  fn try_update( stack : &M::Struct<I>, index : usize, val : &I) -> Result<M::Struct<I>, StackError>
  { let mut acc = M::empty()
  ; let mut cur = stack
  ; let mut i = index
  ; loop { match M::head_tail(cur) {
      None => return Err(StackError::Subscript)
    
    , Some((_head, tail)) if i == 0 
    => return Ok( Self::append(&Self::reverse(&acc), &M::cons(val, tail)) )
    
    , Some((head, tail)) 
    => (acc, cur, i) = ( M::cons(head, &acc) , tail , i-1)
    }}
  }

  /// Exercise 2.1
  fn suffixes<Out>( stack : &M::Struct<I> ) -> M::Struct<M::Struct<I>> 
  where M::Struct<M::Struct<I>>: Clone 
  { let mut acc = M::cons(stack, &M::empty())
  ; let mut cur = stack
  ; loop { match M::head_tail(cur) {
      None => return DefaultStack::<M,M::Struct<I>>::reverse(&acc)
    , Some((_, tail)) 
    => (acc, cur) = (M::cons(tail, &acc), tail) 
    }}
  }
}

impl<Item : Clone> 
Add for &List<Item>
{ type Output = List<Item>
; fn add(self, rhs: Self) -> Self::Output
  { type D<I> = DefaultStack<ListStack, I>
  ; D::<Item>::append( self, rhs )
  }
}


// 2.2 Binary Search Trees ////


trait SET 
{ type Elem
; type Set

; fn empty()-> Self::Set
; fn insert( e : &Self::Elem, s : &Self::Set ) -> Self::Set
; fn member( e : &Self::Elem, s : &Self::Set ) -> bool
;
}

trait ORDERED
{ type T
; fn eq ( x : &Self::T, y : &Self::T) -> bool
; fn lt ( x : &Self::T, y : &Self::T) -> bool
; fn leq( x : &Self::T, y : &Self::T) -> bool 
  { Self::eq(x, y) || Self::lt(x, y) }
}

// this would be kept private
#[derive(Clone)]
enum Tree<Elem>
{ E
, T(RcStrong<(Tree<Elem>, Elem, Tree<Elem>)>)
}

impl<E : Clone> Tree<E>
{ fn new(l : &Self, e : &E, r : &Self) -> Self
  { Tree::T(RcStrong::new((l.clone(), e.clone(), r.clone()))) } 
}

struct UnbalancedSet<Element : ORDERED> (PhantomData<Element>);
impl<Element : ORDERED> SET for UnbalancedSet<Element> where Element::T : Clone
{ type Elem = Element::T
; type Set  = Tree<Self::Elem>

; fn empty()-> Self::Set { Tree::E }
        
  fn member( e : &Self::Elem, s : &Self::Set ) -> bool 
  { let mut cur = s
  ; let mut candidate = None
  ; loop { match cur {
      Tree::E => return candidate.map_or(false, |c| Element::eq(e, c))
    , Tree::T(r) => 
      { let (l, val, r) = r.deref()
      ; if Element::lt(e, val) { cur = l } else 
        { cur = r ; candidate = Some(val) } 
      }
    }}
  
  }

  fn insert( e : &Self::Elem, s : &Self::Set ) -> Self::Set
  { #[derive(Clone, Copy)] enum B<T> {L(T), R(T)} // we use this to track if we took the left or right branch
    use ListStack as LS;
  ; let mut backtrack = LS::empty()
  ; let mut already = None
  ; let mut cur = s
  ; loop { match cur {
      Tree::T(ptr) =>
      { let (l, val, r) = ptr.deref()
      ; if Element::lt(e, val)
        { (cur, backtrack) = (l, LS::cons( &B::L(ptr), &backtrack )) } 
        else 
        { cur = r 
        ; already = Some(val) 
        ; backtrack = LS::cons( &B::R(ptr), &backtrack ) 
        }
      }
    , Tree::E =>
      if  already.map_or(false, |c| Element::eq(e, c))
      { return s.clone() } else { break }
    }}


    let mut acc = Tree::T(RcStrong::new((Tree::E, e.clone(), Tree::E)))
  ; loop { match LS::head_tail(&backtrack) {
      None => return acc
    
    , Some((B::L(head), tail)) =>
      (acc, backtrack) = 
      ( Tree::new(&acc, &head.1, &head.2) 
      , tail.clone()
      )
    
    , Some((B::R(head), tail)) => 
      (acc, backtrack) = 
      ( Tree::new(&head.0, &head.1, &acc)
      , tail.clone()
      )
    }}
  }
}

fn complete<Elem : Clone>( e : &Elem, d : usize ) -> Tree<Elem> 
{ let mut acc = Tree::E
; let mut c   = d
; loop { match c {
    0 => return acc
  , _ => (acc, c) =  (Tree::new(&acc, e, &acc), c - 1)
  }}
}

/* fn create // punt */
#[allow(non_camel_case_types)]
trait FINITE_MAP 
{ type Key
; type Map<T>
; fn empty<V>     ()->Self::Map<V>
; fn bind<V>      (k : &Self::Key, v : &V, m : &Self::Map<V>) -> Self::Map<V> where V : Clone, Self::Key :Clone
; fn lookup<V>    (k : &Self::Key, m : &Self::Map<V>)->V where V : Clone { Self::try_lookup(k, m).expect("Key failed to find a value") }
  fn try_lookup<V>(k : &Self::Key, m : &Self::Map<V>)->Option<V> where V : Clone
;
}


struct UnbalancedFiniteMap<Elem : ORDERED>(PhantomData<Elem>);
impl<E : ORDERED> FINITE_MAP for UnbalancedSet<E>
{ type Key = E::T
; type Map<T> = Tree<(Self::Key, T)>
; fn empty<V>     ()->Self::Map<V> { Tree::E }

  fn bind<V>      (k : &Self::Key, v : &V, m : &Self::Map<V>) -> Self::Map<V> 
  where V : Clone, Self::Key :Clone
  {  #[derive(Clone, Copy)] enum B<T> {L(T), R(T)} // we use this to track if we took the left or right branch
  ; type LS = ListStack
  ; let mut backtrack = LS::empty()
  ; let mut cur = m
  ; let key_value = (k.clone(), v.clone())

  ; let mut acc = 
    loop { match cur {
      Tree::E => break Tree::new(&Tree::E, &key_value, &Tree::E)

    , Tree::T(ptr) => 
      { let p @ (l, (key, _), r) = ptr.deref()
      ; if E::lt(k, key) 
        { (cur, backtrack) = (l , LS::cons(&B::L(p), &backtrack)) }
        else 
        if E::lt(key, k) 
        { (cur, backtrack) = (r , LS::cons(&B::R(p), &backtrack)) }
        else 
        { break Tree::new(l, &key_value, r) }
      }
    }}

  ; loop { match LS::head_tail(&backtrack) {
      None => return acc

    , Some((B::L((_l, kv, r)), tail)) => 
      (acc, backtrack) = ( Tree::new(&acc, kv, r) , tail.clone())

    , Some((B::R((l, kv, _r)), tail)) => 
      (acc, backtrack) = ( Tree::new(l, kv, &acc) , tail.clone())
    }}
  }

  fn try_lookup<V>(k : &Self::Key, m : &Self::Map<V>)->Option<V> 
  where V : Clone
  { let mut cur = m
  ; let mut candidate : Option<&(_, V)> = None
  ; loop { match cur {
      Tree::E =>  return 
      if let Some((key, val)) = candidate
      { E::eq(k, key).then_some(val.clone()) }
      else 
      {None}

    , Tree::T(ptr) => 
      { let (l, kv @ (key, _), r) = ptr.deref()
      ; if E::lt(k, key) 
        { cur = l }
        else
        { (cur, candidate) = (r, Some(kv)) }
      }
    }}  
  }
}

// 3 Some Familiar Structures in a Functional Setting ////


trait HEAP 
{ type Elem : ORDERED
; type Struct

; fn empty    ()->Self::Struct
; fn is_empty ( h  : &Self::Struct ) -> bool

; fn insert   ( e  : &<Self::Elem as ORDERED>::T, h : &Self::Struct ) -> Self::Struct
; fn merge    ( h1 : &Self::Struct, h2 : &Self::Struct ) -> Self::Struct

; fn findMin  ( h  : &Self::Struct ) -> <Self::Elem as ORDERED>::T
  { Self::try_findMin(h).expect("HEAP must be non-empty") }
  fn deleteMin( h  : &Self::Struct) -> Self::Struct
  { Self::try_deleteMin(h).expect("HEAP must be non-empty") }

  fn try_findMin  ( h  : &Self::Struct ) -> Option<<Self::Elem as ORDERED>::T>
; fn try_deleteMin( h  : &Self::Struct) -> Option<Self::Struct>
;
}