�Ƶ��ȥ����ͥ졼��

back [English]

����: ����������ϡ��Ƶ���Ȥ������˸�ΨŪ�˵��ҤǤ��롣 ���������̤Υǡ�������������褦�ʺƵ�Ū��³���ϸ�̩�����椹��ɬ�פ����ꡢ �������ä��ץ�����ߥ󥰤��񤷤���Python 2.2 �ʹߤ�����Ѳ�ǽ�ˤʤä� �����ͥ졼����Ȥ��ȡ��ʷ�ʥ����ɤ�ݻ����Ĥġ� ����������³���򤫤󤿤�����椹�뤳�Ȥ��Ǥ��롣

����ʸ��ǻȤ��Ƥ��륽���������ɤ� �������� �ץ쥤��ƥ������Ǥ� ��������


�Ϥ����

�Ƶ������˶��Ϥʥᥫ�˥���Ǥ��� ���ˤ���Ϻ���򾷤����Ȥ⤢��ޤ������դĤ��Ƶ���Ȥ��ȡ�������ñ�˵��Ҥ��뤳�Ȥ��Ǥ��ޤ��� �����³���������ǡ����̤��ؿ�Ū��������褦�ʾ�硢����ϤȤ��ˤ��ƤϤޤ�ޤ��� �ڹ�¤��õ����������Ǥ��礦���ڤγ������ϤҤȤİʾ�λҤ���äƤ��ޤ����� ���ز��ؤȤ��ɤäƤ����ˤĤ�ơ������ο��ϻؿ�Ū�������Ƥ����ޤ��� �Ǥ⡢�⤷���٤Ƥ����������ͤ�Ʊ������Τ�ΤǤ���С��ޤä���Ʊ����³���� ���٤Ƥ��������Ф��Ƥ��꤫����Ŭ�ѤǤ��ޤ���

�Ǥ��ڤ�õ���Ϥ����餯�ۤɤ�ɤη׻����ʳؤζ��ʽ�� ��������Ƥ���Τǡ����ޤꤪ�⤷�����Ϥ���ޤ��� ï�Ǥ��ڤ�õ������Ȥ��ˤϡ��ۤȤ�ɲ���ͤ����˺Ƶ���Ȥ����ȤǤ��礦�� ���������������Ƶ������Ω�Ĥ褦����Ϥۤ��ˤ���������ޤ��� �����Ǥ����Ǥ��̤���򸫤Ƥߤޤ��礦��

�ʲ��Τ褦�ʴؿ� f ��ͤ��ޤ��� ����ϥ٥��ȥ�ν��� (V1, V2, V3, ... , Vn) ������Ȥ��ƤȤꡢ Vi �γ����Ǥ��Ȥꤦ���Ȥ߹�碌���٤Ƥ���ʤ뽸��� �֤���ΤȤ��ޤ������Τ��Τ��Ȥ߹�碌�ϡ�n���ǤΥ٥��ȥ� (xi1, xi2, ... , xim) ����ʤ�ޤ��������� xij �� Vi �����ǤǤ������δؿ����֤��٥��ȥ�Ϥ���֤� |V1| x |V2| x |V3| x ... x |Vn| �Ĥ��뤳�Ȥˤʤ�ޤ���

���δؿ��� Python �Ǽ������뤳�Ȥ�ͤ��Ƥߤޤ��礦�� ñ�㤵�Τ��ᡢ�����Ǥϥ٥��ȥ� Vi �Τ��Τ��Τ� ɽ���Τ�ʸ���󥪥֥������Ȥ��Ѥ��뤳�Ȥˤ��ޤ��� ���δؿ��ϥ٥��ȥ�ν����ꥹ�ȤȤ����֤����Ȥˤ��ޤ��礦�� ����ȡ�ͽ�ۤ�����̤ϰʲ��Τ褦�ˤʤ�ޤ�:

f([]) --> ['']  # 1
f(['abc']) --> ['a', 'b', 'c']  # 3
f(['abc', 'xyz']) --> ['ax', 'ay', 'az', 'bx', 'by', 'bz', 'cx', 'cy', 'cz']  # 9
f(['abc', 'xyz', '123']) --> ['ax1', 'ax2', 'ax3', 'ay1', 'ay2', 'ay3', 'az1', 'az2', 'az3',
                              'bx1', 'bx2', 'bx3', 'by1', 'by2', 'by3', 'bz1', 'bz2', 'bz3',
                              'cx1', 'cx2', 'cx3', 'cy1', 'cy2', 'cy3', 'cz1', 'cz2', 'cz3']  # 27

�츫����ȡ�����ϴ�ñ�˼����Ǥ������˻פ��뤫�⤷��ޤ��� �⤷������ȺƵ���Ȥ�ʤ��Ƥ��ñ�˽񤱤����˸�����ΤǤϤʤ��Ǥ��礦���� �ǤϤ�äƤߤޤ��礦��


��ˡ

�ǽ�ˡ��⤷�Ƶ���ޤä����Ȥ�ʤ��Ȥ���ȡ� �ץ������Ϥ����餯����ʴ����Τ�Τˤʤ�Ȼפ��ޤ�:

�Ƶ���Ȥ�ʤ��С������

def f0(args):
  counter = [ 0 for i in args ]
  r = []
  while 1:
    r.append("".join([ arg1[i] for arg1,i in zip(args, counter) ]))
    carry = 1
    x = range(len(args))
    x.reverse()  # x == [len(args)-1, len(args)-2, ..., 1, 0]
    for i in x:
      counter[i] += 1
      if counter[i] < len(args[i]):
        carry = 0
        break # "for" ����ȴ����
      counter[i] = 0
    else:
      break # "while" ����ȴ����
  return r

�Ƶ���Ȥ�ʤ���硢�ץ������Ϥ��٤Ƥ��Ȥ߹�碌���������뤿��� ����ξ��֤򲿤餫����ˡ�Ǥ��٤Ƶ������Ƥ����ͤФʤ�ޤ��� ���Υץ������Ǥϡ����û��� (full-adder) �Τ褦�ʤ�Τ򥨥ߥ�졼�Ȥ��ޤ����� �ޤ��ץ������������Υꥹ�Ȥ�������ޤ��������Ƥ��κDz��̤η�� 1 ��ä��褦�Ȥ��ޤ��� �롼�פ��ޤ�뤿�Ӥˡ����δؿ��ϰ������Ϥ��줿���Ǥ��礷���ѿ� r ������Ƥ����ޤ������������Υץ������Τդ�ޤ��ϡ� "carry" �ʤɤΰ�̣��Ĺ���ѿ�̾���ҥ�ȤˤϤʤ��ΤΡ� ���ΤȤ��ƤϤ狼��ˤ�����ΤǤ���

�Ƶ���Ȥä��С������

�ǤϺƵ���Ȥ��Ȥɤ��ʤ�Ǥ��礦�����ؿ� f �ϼ��Τ褦�˺Ƶ�Ū������Ǥ��ޤ�:

f(Vi, Vi+1, ... , Vn) = ({xi1} + f(Vi+1, ... , Vn)) +
({xi2} + f(Vi+1, ... , Vn)) +
...
({xim} + f(Vi+1, ... , Vn)) .

���������ȤäƼ�ʬ���Ȥ�ƤӽФ��褦�ˤ���ȡ��ץ������Ϥ��äȴ�ñ�ˤʤ�ޤ�:

def fr(args):
  if not args:
    return [""]
  r = []
  for i in args[0]:
    for tmp in fr(args[1:]):
      r.append(i + tmp)
  return r

���������ľ��Ū�˼���������ΤǤ��� �Ƶ��������ʤȤ����ϡ���������򤤤��Ĥ��Ρ֥�������פ� ʬ�䤷�������γƥ�������ˤ�ޤä���Ʊ����³�����Ȥ��뤳�ȤǤ��� ���Υץ������Ǥ�ñ�˳ư����κǽ�����Ǥ�ȤäƤ��ơ� ����򤳤δؿ����Ȥ�ҤȤľ��ʤ������ǸƤӤ������Ȥ��� ���٤Ƥ��֤��ͤ��ɲä��Ƥ��ޤ� (�� 1)��


�� 1. �Ƶ���Ȥä��С������

����ʤ��ˡ

����ޤǸ��Ƥ����ؿ��ϡ������򤤤äڤ���֤��褦�ʤ�ΤǤ����� ������õ��������夲�ʤɤΥ��ץꥱ�������ˤ�äƤϡ� ����餹�٤Ƥ��Ȥ߹�碌��Ф��Ƥ���ɬ�פ��ʤ����⤢��ޤ��� ��ꤿ���Τϡ����Τ��Τ��Ȥ߹�碌�򤿤��������ơ� �Ѥ��Ѥ���餽���ϼΤƤ�褦�ˤ������ΤǤ���

���Ϥο������ʤ��Ȥ��ˤϡ�������礷������ǤϤ���ޤ��� �Ǥ�Ƶ�Ū��³���Ǵ��ԤǤ���Τϡ����η�̤��ؿ�Ū��������褦�ʾ��Ǥ����� �Ȥ����������ʤ��Ȥˡ����Τ褦�ʴؿ��ϤդĤ����ʤ����̤ν��Ϥ��������ޤ��� ���������Ǥ���¿���θ�������Ǥϡ������ν��Ϥ��٤Ƥ򵭲����뤳�Ȥ� �Ǥ��ޤ��󡣤�������Ϥ䤫�졢�������̤θ³�����ã���Ƥ��ޤ����ȤǤ��礦:

$ ulimit -v 5000
$ python
...
>>> for x in fr(["abcdefghij","abcdefghij","abcdefghij","abcdefghij","abcdefghij"]):
...  print x
...
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 7, in fr
MemoryError

������Ф���ŵ��Ū�ʲ�ˡ�ϡ������򤹤٤ưۤʤ���֤��ڤ�櫓�뤳�ȤǤ��� Python �Ǥϡ�����ϥ��ƥ졼����ȤäƹԤ��ޤ���

���ƥ졼����Ȥä��С������

Python �Ǥ� __iter__ �᥽�åɤ��ĥ��饹�� ���ƥ졼���Ȥ��ƻȤ����Ȥ��Ǥ��ޤ������ƥ졼���ϵ�ǽŪ�˥ꥹ�Ȥ� �ޤä���Ʊ���ǤϤʤ���ΤΡ������Ĥ��δؿ����뤤��ʸ�Ǥ� ���ƥ졼����ꥹ�ȤΤ����˼�뤳�Ȥ��Ǥ��ޤ� (for, map, filter �ʤ�)��

class fi:
  def __init__(self, args):
    self.args = args
    self.counter = [ 0 for i in args ]
    self.carry = 0
    return
  
  def __iter__(self):
    return self
  
  def next(self):
    if self.carry:
      raise StopIteration
    r = "".join([ arg1[i] for arg1,i in zip(self.args, self.counter) ])
    self.carry = 1
    x = range(len(self.args))
    x.reverse()  # x == [len(args)-1, len(args)-2, ..., 1, 0]
    for i in x:
      self.counter[i] += 1
      if self.counter[i] < len(self.args[i]):
        self.carry = 0
        break
      self.counter[i] = 0
    return r

# display
def display(x):
  for i in x:
    print i,
  print
  return

���Υץ������Ǥϡ����饹 fi �Υ��󥹥ȥ饯���� �Ƶ��С������δؿ� fr ��Ʊ�ͤ˰ʲ��Τ褦�ˤ��ƻȤ����Ȥ��Ǥ��ޤ�:

>>> display(fi(["abc","def"]))

���Υ��󥹥��󥹤� for ʸ���Ϥ����ȡ� __iter__ �᥽�åɤ��ƤФ졢�����֤��� (�����ǤϤ��Υ��󥹥��󥹼���) �� �롼�פΥ��ƥ졼���Ȥ��ƻȤ��ޤ������롼�פ�ޤ�뤿�Ӥ˥��ƥ졼���� next �᥽�åɤ������ʤ��ǸƤФ졢�����֤��ͤ��롼���ѿ��˳�Ǽ����ޤ���

�����������Υץ����������򤹤�ΤϤ����䤵�����Ϥ���ޤ��� ���르�ꥺ��Ū�ˤϡ��������ˤ������Ƶ���Ȥ�ʤ��С������� ���Ƥ��ޤ���next ���ƤФ�뤿�Ӥˡ�������ѿ� counter �˳�Ǽ����Ƥ��븽�ߤξ��֤򹹿����� ���ξ��֤˱�������̤�ҤȤ��֤��ޤ����Ǥ⤳��Ϥ���� �������äƤ���褦�˸�����Ǥ��礦���ʤ��ʤ餳�Υ᥽�åɤ� �롼�פ���ǸƤФ��褦�ˤǤ��Ƥ��ޤ��������Υ롼�׼��Τ� �����ˤ�����Ū�˸���ʤ�����Ǥ����ɼԤϤ����餯���Υ᥽�åɤ� �����ʤ��ѿ� carry ������å����Ƥ���Τ� �̤��餦���⤷��ޤ��󡣤�������򤹤�ˤϡ����Υ᥽�åɤ� ��¦�ˤ���롼�� (�����ʤ�) ����������ɬ�פ�����ΤǤ���

�����ͥ졼����Ȥä��С������

�Ǥϥ����ͥ졼����ȤäƤߤޤ��礦���ץ������Ϥ���˴�ñ�ˤʤ�ޤ�:
def fg(args):
  if not args:
    yield ""
    return
  for i in args[0]:
    for tmp in fg(args[1:]):
      yield i + tmp
  return

����ϥ��ƥ졼���Ǥ����ñ�Ǥ�������Ǥʤ��� �Ƶ���Ȥä����ꥸ�ʥ�ΥС��������⤵��˴�ñ�ˤʤäƤ��뤳�Ȥ� ���Ť��ޤ��������ͥ졼����Ȥ��ȡ���̤���ˤҤȤĤ��Ĥ�����ꤲ�Ƥ��� (���뤤�� "yield ���Ƥ���") �����Ǥ褯���ꤲ�����Ȥ�˺��뤳�Ȥ��Ǥ��ޤ��� ����Ϸ�̤򥹥ȥ꡼��ǥХ�����ɽ������Τ˻��Ƥ��ޤ��� ���֤���¸����褦����Ĥ���ɬ�פϤ���ޤ��� �������٤Ƥη�̤򲿤�ͤ�����������������Ǥ��Ƥʤ����� ��³�����Ф��Ƹ�̩�ʥ���ȥ������ݻ��Ǥ���ΤǤ��� ������ǽ�Ϥ����Ĥ��δؿ�������ǥ��ݡ��Ȥ���Ƥ�����ٱ�ɾ�� (lazy evaluation)�פǤ�¸��Ǥ��뤳�Ȥ˵��Ť���뤫�⤷��ޤ��� �ٱ�ɾ���ȥ����ͥ졼���Ϥޤä���Ʊ����ΤǤϤ���ޤ��󤬡� �����Ϥɤ����Ʊ��������٤Ĥ٤ĤΤ�����ǽ�������Τ���Ω���ޤ���

Lambda ���ץ��벽�С������

�ؿ����ץ�����ߥ󥰤˴���Ƥ���ͤǤ���С� ���֥������Ȥ��� lambda ���ˤ�륫�ץ��벽�򹥤फ�⤷��ޤ��� Python �ǤϤ�����ǽ�Ǥ����������ºݤˤϡ�����Ϥ��ʤ�ऺ�������ѥ���Ǥ����� ���ƥ졼����Ʊ��������Ǥ�Ǥ����ΤǤ����������ǤϤޤä����̤���ˡ�� ��Ƥߤ褦�Ȼפä��ΤǤ��������֤ˤ錄���Ժ����Τ������ǽ�Ū�� �Ǥ����Τϼ��Τ褦�ʤ�ΤǤ���:

def fl(args, i=0, tmp="", parent_sibling=None):
  if not args:
    # �դˤ���
    return (tmp, parent_sibling)
  if i < len(args[0]):
    # �٤����� (����, sibling) �����
    sibling = fl(args, i+1, tmp, parent_sibling)
    return lambda: fl(args[1:], 0, tmp+args[0][i], sibling)
  else:
    # �ҤȤľ夬�äƿƤη���򤿤��ͤ�
    return parent_sibling

# lambda �С�������õ���롼����
def traverse(n):
  while n:
    if callable(n):
      # ����
      n = n()
    else:
      # ��
      (result, n) = n
      print result,
  print

����Ū�ʥ����ǥ��ϡ�������������ڤ�õ���Ȥ��ư����Ȥ�����ΤǤ��� �ؿ� f �ϳ���������ʬŪ�ʲ���ä��ڤȤ��Ƥߤ뤳�Ȥ��Ǥ��ޤ� (�� 2)�� fl ���֤��ؿ��Ϥ��ΰ��֤��٤����� (sibling)������� �Ƥ��������٤��������ݻ����Ƥ��ޤ������δؿ����ڤ򲼤äƤ����ˤĤ�� �٥��ȥ�����Ǥ��ɲä���Ƥ����ޤ������줬�դˤĤ����Ȥ��� ���δؿ��ϤҤȤĤδ����ʲ� (�Ȥ߹�碌) ���ˤ��Ƥ���Ϥ��Ǥ��� Ʊ���⤵�ˤ⤦����ʾ�õ�����٤��������ʤ���硢�ؿ��ϤҤȤľ�˾夬�ä� �Ƥ��٤ؤȿʤߤޤ��������ڤ�õ������ˤ����̤��Ѱդ��줿 �ؿ� (�ɥ饤��) ��ɬ�פˤʤ�ޤ���


Fig 2. The Function f as Tree Traversal

������󡢥����ͥ졼���ǤǤ��ڤ�õ���򤪤��ʤ����ȤϤǤ��ޤ��� ���ξ�硢�ڤγ������Ƿ�̤��ꤲ�Ƥ����Ȥ������Ȥˤʤ�Ǥ��礦��


Yusuke Shinyama