<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div class="">Hello fellow evolutionists,</div>
<div class=""><br class="">
</div>
<div class="">I’m not sure this list is the best place to talk about this, so please redirect me if it should be discussed elsewhere.</div>
<div class=""><br class="">
</div>
<div class="">While trying to implement algebraic data types in Swift, I stumble upon an interesting problem. Let’s consider the following example:</div>
<div class=""><br class="">
</div>
<div class="">
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">protocol</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Term {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">struct</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Zero:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">struct</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Succ:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> pred:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> term:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Zero</span><span style="font-variant-ligatures: no-common-ligatures" class="">()</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">for</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">_</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">in</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">0</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..<
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">20000</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Succ</span><span style="font-variant-ligatures: no-common-ligatures" class="">(</span><span style="font-variant-ligatures: no-common-ligatures" class="">pred:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">term</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
</div>
<div class=""><br class="">
</div>
<div class="">This code will take forever to execute (about 1 minute on my mbp late 2013), whereas if I replace the structures with reference types it will finish almost instantly, which is what one would expect from such a simple data structure. Most likely,
the problem lays in the fact that a deep copy is produced every time a new level of recursion is created. However, I guess this case could be detected by the compiler, as the `term` variable passed as parameter is immediately affected to the rvalue of the
expression using it.</div>
<div class=""><br class="">
</div>
<div class="">An even more powerful approach would be to keep track of the reference on the original `term` value under the hood, and update it if necessary in a copy-on-write fashion. As I understand it, this would enable this code to be efficiently executed
as well:</div>
<div class=""><br class="">
</div>
<div class="">
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">protocol</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Term {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">struct</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Leaf:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">struct</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Tree:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> left:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> right:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> tree:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Leaf</span><span style="font-variant-ligatures: no-common-ligatures" class="">()</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">for</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">_</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">in</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">0</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..<
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">20000</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">tree</span><span style="font-variant-ligatures: no-common-ligatures" class=""> =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Tree</span><span style="font-variant-ligatures: no-common-ligatures" class="">(left:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">tree</span><span style="font-variant-ligatures: no-common-ligatures" class="">, right:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">tree</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
</div>
<div class=""><br class="">
</div>
<div class="">Interestingly, while enumerations are value types, indirect enumerations don’t suffer the performance issue of the above examples. Note however that the issue will reappear if the enum isn’t marked `indirect`.</div>
<div class=""><br class="">
</div>
<div class="">
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">protocol</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Term {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(186, 45, 162);" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">indirect</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">
</span><span style="font-variant-ligatures: no-common-ligatures" class="">enum</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> Nat:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">case</span><span style="font-variant-ligatures: no-common-ligatures" class=""> zero</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">case</span><span style="font-variant-ligatures: no-common-ligatures" class=""> succ(</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> term =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Nat</span><span style="font-variant-ligatures: no-common-ligatures" class="">.</span><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">zero</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">for</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">_</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">in</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">0</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..<
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">20000</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> = .</span><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">succ</span><span style="font-variant-ligatures: no-common-ligatures" class="">(</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">term</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
</div>
<div class=""><br class="">
</div>
Thanks,
<div class="">Dimitri Racordon<br class="">
<br class="">
</div>
</body>
</html>