unfold に挑戦

id:NyaRuRu:20070722#p2 のお題がおもしろいので、unfold 書いてみました。Orcas 立ち上げるのが面倒だったので C#2.0 で。
コードは最後にして、その前にいろいろと。

unfold ???

まずは unfold が何なのかわからなかったので Haskell の定義から。Hugs の List.hs から引用。
名前からして fold の反対だろうとは思うけど、畳み込みの反対って余計想像できなかったりｗ

unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b  =
  case f b of
   Just (a,new_b) -> a : unfoldr f new_b
   Nothing        -> []

Haskell には unfoldr がありました。foldr、foldl はありますが、unfoldl はなさそう。
関数を次々と評価してリストを生成する機能だそうです。unfoldr の一つ目の引数「(b -> Maybe (a, b))」は「bを引数とし、戻り値 Maybe (a, b) を返す 関数」です。二つ目の引数(に見えるもの)は 種となる b。戻り値は、リスト [a] 。a と b はテンプレートの型パラメータにあたります。Maybe は C# の Nullable みたいなもの。でも、ずっと強力。詳しくは「ふつうのHaskellプログラミング」の266ページを。(a, b)はタプルでC++のpair。

NyaRuRuさんの記事にある、F# の unfold を使ったフィボナッチを Haskell にしてみます。F# のコードははじめて見たけど、たぶんこういうことだと思う。

fib = unfoldr ( \( x, y ) -> Just ( x, ( y, x + y ) ) ) ( 1, 1 )

実行は take 20 fib で。結果はあってるので、よさげ。久しぶりの Haskell ですっかりいろいろ忘れてて大変でした…。

で、unfold の肝は「いかに終了をきれいに扱うか」だと思うので、フィボナッチだと無限に続いて終わらないので別の終わる例を。

tails

Haskell本をパラパラ開いて、tails 関数がよさげだったので例に取り上げます。まずは GHCi での実行例から。

*Main> tails "hoge"
["hoge","oge","ge","e",""]
*Main> tails [1,2,3]
[[1,2,3],[2,3],[3],[]]

与えられたリストから一つずつ要素を削っていき、そのリストを返します。なんでこんなものが標準ライブラリにあるのかさっぱりですが、急須を一命令で描けたりする世界もあることだし気にしない方向で。

これを unfold を使って書いてみます。

sioTails = unfoldr pat
  where
    pat [] = Nothing
    pat (x:xs) = Just ( x:xs, xs )

実行結果はこう。

*Main> sioTails "hoge"
["hoge","oge","ge","e"]
*Main> sioTails [1,2,3]
[[1,2,3],[2,3],[3]]

本物と比べると最後の [] が抜けてます。でも、unfold を試すだけなら困らないのでこれを C# でやってみます。

いよいよ C#

using System;
using System.Collections.Generic;

namespace unfold
{
  using PairString = KeyValuePair<string, string>;
  using NullablePairString = Nullable<KeyValuePair<string, string>>;
  using PairSeq = KeyValuePair<IEnumerable<int>, IEnumerable<int>>;
  using NullablePairSeq = Nullable<KeyValuePair<IEnumerable<int>, IEnumerable<int>>>;
  using PairInt = KeyValuePair<int, int>;
  using PairPairInt = KeyValuePair<int, KeyValuePair<int, int>>;
  using Result = Nullable<KeyValuePair<int, KeyValuePair<int, int>>>;

  delegate R Func<A, R>( A a );

  class Program
  {
    static void Main()
    {
      // sioTails "hoge"
      IEnumerable<string> tails = Unfoldr<string, string>(
        delegate( string s )
        {
          if ( string.IsNullOrEmpty( s ) ) return null;
          return new NullablePairString( new PairString( s, s.Substring( 1 ) ) );
        },
        "hoge" );

      foreach ( string s in tails )
        Console.Write( s + ", " );
      Console.WriteLine();

      // sioTails [1,2,3]
      IEnumerable<IEnumerable<int>> tails2 = Unfoldr<IEnumerable<int>, IEnumerable<int>>(
        delegate( IEnumerable<int> seq )
        {
          using ( IEnumerator<int> it = seq.GetEnumerator() )
          {
            if ( !it.MoveNext() ) return null;
          }
          return new NullablePairSeq( new PairSeq( seq, Skip( seq, 1 ) ) );
        },
        new int[] { 1, 2, 3 } );

      foreach ( IEnumerable<int> seq in tails2 )
      {
        Console.Write( "[" );
        foreach ( int n in seq )
          Console.Write( n + ", " );
        Console.Write( "], " );
      }
      Console.WriteLine();

      // fib = unfoldr ( \( x, y ) -> Just ( x, ( y, x + y ) ) ) ( 1, 1 )
      // take 20 fib
      IEnumerable<int> fib = Unfoldr<PairInt, int>(
        delegate( PairInt pair )
        {
          return new Result(
            new PairPairInt( pair.Key,
              new PairInt( pair.Value, pair.Key + pair.Value ) ) );
        },
        new PairInt( 1, 1 ) );

      int count = 20;
      foreach ( int n in fib )
      {
        if ( count <= 0 ) break;

        count--;
        Console.Write( n + ", " );
      }
      Console.WriteLine();
      Console.ReadKey();
    }

    static IEnumerable<R> Unfoldr<A, R>( Func<A, Nullable<KeyValuePair<R, A>>> f, A a )
    {
      while ( true )
      {
        Nullable<KeyValuePair<R, A>> pair = f( a );

        if ( !pair.HasValue ) yield break;

        yield return pair.Value.Key;
        a = pair.Value.Value;
      }
    }
  }
}

う〜、やっぱりC#3.0で書けばよかった。2.0だと汚くなりすぎ…。
Skip関数は割愛。LINQ相当のものをご想像願います。
実行結果。

hoge, oge, ge, e,
[1, 2, 3, ], [2, 3, ], [3, ],
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
 6765,

Unfoldr に渡す関数では戻り値に Nullable を被せて、Unfoldr でそれを剥ぐという、いまいちな作り。
Maybe モナド構造体を書いてみようと挑戦したけど、やっぱり無理でした。「(Just x) >>= f = f x」と「Nothing >>= f = Nothing」をなんとか書けないものかな。それとも全然別のうまい手がないかなぁ。