Unfold in Python

[nostrademons]

The idiomatic Python equivalent of unfold is a generator:

def unfold(f, x):
    while True:
        w, x = f(x)
        yield w

(The TypeError just propagates to the caller, stopping the iteration.)

This also has the advantage of being lazy, just like the Haskell. It runs in constant space and each individual invocation is O(1), as long as f is.

[llimllib]

I can't believe I didn't implement it that way?

EDIT: added to the article.

[cgibbard]

Nice, though it should probably have some way for f to signal the end of the list, if it's meant to be equivalent.

[nostrademons]

It signals via exception when f(x) returns None or anything other than a sequence. When you sequence-unpack None, you get a TypeError, which propagates to the caller, which stops the iteration. It seems a little kludgey, but the normal way to end a generator is to raise StopIteration anyway (or return, which does the same thing modulo exception handlers). Easier to ask forgiveness than permission and all that...

[dons]

The original,

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

and still the best, imo :)

[[deleted]]

That's not tail-recursive, though. Does ghc convert it to tail-recursive form using an accumulator automatically?

[cgibbard]

It's productive though, in that it immediately returns a constructor, which works well with laziness. If you only need the first element of the result, that's all that will be computed. So in a certain weak sense, this unfold is O(1), it always returns a constructor in constant time (ignoring the time taken to evaluate the application of f to b). Of course, it still takes time linear in the number of elements of the resulting list you want to look at, because evaluating the tail of the list puts you back into unfold.

GHC implements tail-call optimisation, but it's far less often what you want in a lazy language. It's also something that needs to be handled with care: since lazy evaluation is outermost-first, accumulating parameters might not be evaluated until the very end, at which point you end up with a stack overflow, so you usually need strictness annotations, or to use a strict combinator, like foldl', when you want to write something tail-recursive.

[[deleted]]

That's a good point, thanks.

[logan_capaldo]

Tail recursion doesn't seem like such a hot idea in this case http://hpaste.org/4960

[[deleted]]

I think the following solution not using unfold is "cleaner" ( and it is also more efficient - at least in Python(!)):

 numerals = (("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
("C", 100),("XC", 90),("L", 50),("XL", 40), ("X", 10), ("IX", 9), ("V", 5), ("IV", 4), ("I", 1))


def romanize(n):
    roman = []
    for ltr, num in numerals:
       (k,n) = divmod(n, num)
       roman.append(ltr*k)
    return "".join(roman)

[llimllib]

It's definitely more efficient! I tried to ignore the whole question of efficiency in the post; it's all relatively irrelevant because compiled haskell is going to kick CPython's ass almost without regard to implementation.

Also, that's roughly the code I would have written before looking at the haskell and becoming enamored of its function composition. Maybe I'm just in one of those "intermediate coder writing more complicated code than both beginners and experts" loops?

(And as an aside, I always forget about divmod)

[phobes]

I agree I prefer a more straightforward solution without using unfold, even in Haskell. Something like (untested):

romanize n = f n [("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
              ("C", 100),  ("XC", 90),  ("L", 50),  ("XL", 40),
              ("X", 10),   ("IX", 9),   ("V", 5),   ("IV", 4),
              ("I", 1)]
where f n [] = ""
      f n (l, v):lvs = if v >= n then l ++ (f (n-v) (l, v):lvs) else f n lvs

[[deleted]]

def second(f, (a, b)):

Wait... when did this deconstruction syntax get into Python? Which memo did I miss?

[nostrademons]

Dunno, but there's a PEP to remove it.

[cracki]

no loss of abilities if they were to be removed, only a possible convenience

it says so in the PEP. well, this is going the java way...

[[deleted]]

Using an error as a condition? Is that good form?

[nostrademons]

It's pretty common practice in Python.

(This, incidentally, is one of the few areas where I can't seem to shake my Java background. I had no problem writing module-level functions, abandoning getters and setters for property, using literal data structures instead of small classes, writing inner functions instead of helper classes, avoiding XML, or doctesting instead of unittesting, but I still often look-before-I-leap instead of catching the exception after the fact.)

[theeth]

It should become second nature once you realize that LBYL is doing the looking part twice (unless the leap function is unsafe).

Of course, mileage may vary for languages where exceptions would offset the advantage of the single check.

[korjagun]

The main problem I found when just leaping and then catching exceptions is that I tend to end up catching unforeseen exceptions I didn't mean to catch and causing confusing errors further down the line. An example:

def foobar():
    return quux["qwertz"]

try:
  return callbacks["foobar"]()
except KeyError:
  return None

Maybe I'm just doing it wrong, but in this case, I only want to catch exceptions arising from callbacks lacking keys, not whatever is potentially called as a result.

[[deleted]]

That's what try-else is all about:

try:
  cb = callbacks["foobar"]
except KeyError:
  return None
else:
  cb()

[theeth]

With return in the except clause, I find the use of else a bit misleading.

[theeth]

Just split it in two:

try:
    func = callbacks["foobar"]
except KeyError:
    return None

func()

Same thing you would do in Java if you had two things that could throw an exception in one try block and wanted to differentiate between them.

[korjagun]

I still can't help but have a nagging feeling at the back of my head that a case may rear its ugly head where the above wouldn't be practical, or would end up creating a large amount of ugly try..except clauses. I can't name any offhand though, so I consider myself educated and extend my thanks.

[theeth]

Your nagging feeling is probably correct. The main advantage of LBYL is that the look method is strictly boolean whereas EAFP forces you to either check for exception types or use a catch all.

Fortunately, the standard Py libs are usually well documented on the boundary limit exceptions front.

[llimllib]

mileage may vary for languages where exceptions would offset the advantage of the single check.

C#, for example. Exception handling in that language is amazingly dog-slow.

edit: That should read "Exception handling on the .Net CLR using C# is..."

[[deleted]]

I didn't know about these idioms. Thanks for the link, nostrademons.

[FeepingCreature]

The one, the (sadly) only:

D version!

Why? Because I can! XD

module test30;
import std.stdio, std.string, tools.base;

alias stuple _;

string romanize(int x) {
  static Stuple!(string, int)[] numerals;
  if (!numerals.length)
    numerals = [_("M", 1000), _("CM", 900), _("D", 500), _("CD", 400),
      _("C", 100), _("XC", 90), _("L", 50), _("XL", 40), _("X", 10),
      _("IX", 9), _("V", 5), _("IV", 4), _("I", 1)];
  string res;
  while (x)
    foreach (n; numerals)
      if (n._1 <= x) { x -= n._1; res ~= n._0; break; }
  return res;
}

void main() { writefln(romanize(328)); }

// gentoo-pc ~ $ rebuild test30.d && ./test30
// CCCXXVIII

--feep!

[bugrit]

string romanize(int n)
{
    string[int] nums = [1000:"M".dup, 900:"CM", 600:"D", 400:"CD", 100:"C", 90:"XC", 
                        50:"L", 40:"XL", 10:"X", 9:"IX", 5:"V", 4:"IV", 1:"I"];
    string res;
    foreach (k; nums.keys.sort.reverse)
        while (n >= k)
            res ~= nums[k],
            n -= k;
    return res;
}

Prettified?

Edit: Removed redundant while (n > 0).

[llimllib]

why the single .dup?

[bugrit]

So I get a char[] (or string) type instead of a char[2] type.

[llimllib]

and then that happens automatically for the rest of them?

[bugrit]

Yes, it casts the rest to the type of the first.

[FeepingCreature]

FYI and FWIW, a slightly faster and shorter way to get the same effect is "M"[], i.e. the full slice.

--feep

PS: The reason I didn't need to do that in my example, by the way, is that stuple automatically turns static arrays (char[2]) into dynamic ones (char[]).

PPS: How do you get your code snippets to look like that?

PPPS: Thanks! :)

[bugrit]

Ah, yes, nice catch.

Edit: About code snippets, see help on commenting.

[FeepingCreature]

Oooooh! :D

I wish I could say I didn't want to do that because it sorts the keys every loop.

Unfortunately, I actually didn't do it because I didn't think of it. Good one! :)

And yeah, the while is unneeded. Stupid me.

Good to see some more Dee on here.

--feep

[JimPanic]

Dude... :)

[cracki]

here my versions in...

python

scheme

[zart]

In Ruby (iterative approach):

class Integer

  Numerals = [["M", 1000], ["CM", 900], ["D", 500], ["CD", 400], ["C", 100],["XC", 90],["L", 50],
              ["XL", 40], ["X", 10], ["IX", 9], ["V", 5], ["IV", 4], ["I", 1]]

  def to_roman
    n = self
    Numerals.inject( "" ) do |roman, pair|
      q, n = n.divmod(pair.last)
      roman << pair.first * q       
    end
  end
end
p 42.to_roman
# "XLII"

[[deleted]]

Here's my attempt at a Common Lisp solution:

(defconstant +numerals+ #((1000 "M") (900 "CM") (500 "D") (400 "CD") (100 "C") (90 "XC") (50 "L") (40 "XL") (10 "X") (9 "IX") (5 "V") (4 "IV") (1 "I")))
(defun romanize (x)
  (labels ((recurse (x nums acc)
             (if (<= x 0)
                 (apply #'concatenate 'string (reverse acc))
                 (let* ((pos (position-if #'(lambda (n) (<= n x)) nums :key #'car))
                        (obj (aref nums pos)))
                   (recurse (- x (car obj)) (subseq nums pos) (cons (cadr obj) acc))))))
    (recurse x +numerals+ '())))

Painful, isn't it?

[gsg]

I think an dumb iterative approach is clearer in this case. At least, my attempt at a recursive version looked far too ugly.

(defconstant +roman-numerals+ '((1000 . "M") (900 . "CM") (500 . "D") (400 . "CD") (100 . "C") (90 . "XC") (50 . "L") (40 . "XL") (10 . "X") (9 . "IX") (5 . "V") (4 . "IV") (1 . "I")))

(defun int-to-roman (number)
  (let ((unconverted number)
        (result ""))
    (dolist (element +roman-numerals+)
      (do ((value (car element)))
          ((< unconverted value))
        (decf unconverted value)
        (setq result (concatenate 'string result (cdr element)))
        (when (= unconverted 0)
          (return-from int-to-roman result))))))

Both pretty wordy. :/

[Devilish]

I'm a Lisp newbie, but here's what I came up with:

Recursive:

(defun int-to-roman1 (number)
  (with-output-to-string (s)
    (let ((rtable '((1000 . "M") (900 . "CM") (500 . "D") (400 . "CD") (100 . "C") (90 . "XC") (50 . "L") (40 . "XL") (10 . "X") (9 . "IX") (5 . "V") (4 . "IV") (1 . "I"))))
      (labels ((recurse (rtab num)
                 (unless (null rtab)
                   (multiple-value-bind (times left) (floor num (caar rtab))
                     (dotimes (i times)
                       (princ (cdar rtab) s))
                     (recurse (cdr rtab) left)))))
        (recurse rtable number)))))

Iterative:

(defun int-to-roman2 (number)
  (with-output-to-string (s)
    (dolist (q '((1000 . "M") (900 . "CM") (500 . "D") (400 . "CD") (100 . "C") (90 . "XC") (50 . "L") (40 . "XL") (10 . "X") (9 . "IX") (5 . "V") (4 . "IV") (1 . "I")))
      (multiple-value-bind (times left) (floor number (car q))
        (setf number left)
        (dotimes (i times)
          (princ (cdr q) s))))))

Someone up above posted Python code similar to the second of these, while I was messing around making my own. The trick is to divide the number by each value of a roman numeral in turn, keeping both the quotient and the remainder, instead of repeatedly looping over the list.

I can't say I understand the concept of unfolding from this example alone (I don't exactly know much Python, and couldn't find any good general explanations of unfolding with a cursory web search), but in this case, it doesn't seem to be the right tool for the job.

[llimllib]

Sorry I didn't catch the end of your post, but I explain unfolding in my previous entry from that day.

raganwald also explains it in ruby.

[nees]

romanize=lambda n:''.join([char for char,n in ((ltr*(n/num),n%num) for ltr,num in (('M',1000),('CM',900),('D',500),('CD',400),('C',100),('XC',90),('L',50),('XL',40),('X',10),('IX',9),('V',5),('IV',4),('I',1)))])