Simple Cell recomputation

Cell.idr

data Recomputation a  = Same a
                      | Different a

data Cell : Type where
  MkCell : Eq b => (computation : (a -> b)) -> (value : Recomputation (a, b)) -> Cell

recompute : Cell -> Cell
recompute (MkCell computation (Same x)) = MkCell computation (Same x)
recompute (MkCell computation (Different (a, b))) =
  let
    result = computation a
  in
    case result == b of
      True => MkCell computation (Same (a, b))
      False => MkCell computation (Different (a, result))

testCell : Cell
testCell = MkCell negate (Different (1, 2))

nextCell : Cell
nextCell = recompute testCell
-- Which results in `MkCell negate (Different (1, -1))`

Or way cleaner:

data Cell : (a : Type)  -> (b : Type) -> Type where
  Same      : Eq b => (input : a)
                   -> (output : b)
                   -> (computation : (a -> b))
                   -> Cell a b
  Different : Eq b => (input : a)
                   -> (output : b)
                   -> (computation : (a -> b))
                   -> Cell a b

recompute : Cell a b -> Cell a b
recompute (Same input output computation) = Same input output computation
recompute (Different input output computation) =
  let result = computation input
  in if result == output then Same input output computation
                         else Different input result computation

input : Cell a b -> a
input (Same input _ _) = input
input (Different input _ _) = input

output : Cell a b -> b
output (Same _ output _) = output
output (Different _ output _) = output

testCell : Cell Int Int
testCell = Different 1 2 negate

nextCell : Cell Int Int
nextCell = recompute testCell

finalCell : Cell Int Int
finalCell = recompute nextCell

…and the exact same thing in JavaScript (hey, when you use it with the right mindset, it is not such a terrible language):

const recompute = ({different, input, output, computation}) => {
  if (different) {
    const result = computation(input)

    if (result === output) {
      return {different: false, input, output, computation}
    } else {
      return {different, input, output: result, computation}
    }
  } else {
    return {different, input, output, computation}
  }
}

const input = ({input}) => input
const output = ({output}) => output

const testCell = {
  different: true,
  input: 1,
  output: 2,
  computation: x => -x
}

const nextCell = recompute(testCell)
const finalCell = recompute(nextCell)

module.exports = {
  recompute,
  input,
  output,
  testCell,
  nextCell,
  finalCell
}

And Ruby, because why not:

class Cell
  attr_reader :different, :input, :output, :computation

  def initialize different, input, output, computation
    @different = different
    @input = input
    @output = output
    @computation = computation
  end

  def recompute
    if @different
      result = @computation.call input
      if result != @output
        return Cell.new true, @input, result, @computation
      else
        return self
      end
    else
      return self
    end
  end
end

testCell = Cell.new true, 1, 2, proc { |x| -x }
nextCell = testCell.recompute
finalCell = nextCell.recompute

I’m just noticing a couple of things about the languages:

• Idris is pretty terse, but it has some trivial repetition, in this case because of case splitting between constructors.
• JavaScript is the shortest but because it ends up being just a bunch of functions, without any data structure specification. It’s also surprisingly easy, since there are no restrictions to bear in mind. Like play-doh.
• Ruby is verbose and it reads a little clunky when declaring classes, but can be used to good effect for this.

Obviously the ideal would be that Same and Different are guaranteed by the type to be valid, so that you can’t construct a Same cell if (computation input) != output.

My Java is rusty:

interface Computable {
  public Object compute (Object argument);
}

abstract class Cell {
  private Computable computation;
  private Object input;
  private Object output;

  public Computable getComputation () {
    return computation;
  }

  public Object getInput () {
    return input;
  }

  public Object getOutput () {
    return output;
  }
}

class SameCell extends Cell {
  public SameCell (Object input, Object output, Computable computation) {
    this.input = input;
    this.output = output;
    this.computation = computation;
  }

  public Cell compute () {
    return this;
  }
}

class DifferentCell extends Cell {
  public DifferentCell (Object input, Object output, Computable computation) {
    this.input = input;
    this.output = output;
    this.computation = computation;
  }

  public Cell compute () {
    Object result = this.computation.compute(this.input);

    if (result == this.output) {
      return new SameCell(this.input, this.output, this.computation);
    } else {
      return new DifferentCell(this.input, result, this.computation);
    }
  }
}

Modern PHP (super rusty too):

<?
$recompute = function ($cell) {
  if ($cell['different'] == true) {
    $result = $cell['computation']($cell['input']);

    if ($result == $output) {
      return array(
        'different' => false,
        'computation' => $cell['computation'],
        'input' => $cell['input'],
        'output' => $cell['output']
      );
    } else {
      return array(
        'different' => true,
        'computation' => $cell['computation'],
        'input' => $cell['input'],
        'output' => $result
      );
    }
  } else {
    return $cell;
  }
};

$testCell = array(
  'different' => true,
  'computation' => function ($int) { return -$int; },
  'input' => 1,
  'output' => 2
);
$nextCell = $recompute($testCell);
$finalCell = $recompute($nextCell);

var_dump($testCell);
var_dump($nextCell);
var_dump($finalCell);
?>