CODEWITHSUNDEEP
fibonacciapl
RI Swamp Yankee
RI Swamp Yankee

Reputation: 173

Generate a fibonacci series with no loops or flow control in APL

Is there a way to create a fibonacci sequence in APL with a one-liner that doesn't require loops or flow control?

I've done it with a function using → and a conditional test, but I feel there must be a more elegant, declarative way. An example that I've found that claims to do it on one line doesn't work on gnu-apl - it seems it's on the right track, using matrix math, but I'm having a hard time following along, and can't tweak it to work correctly.

I'm pursuing APL as my first real programming language (I love the symbols. I just do.) I'm now using Project Euler as a way to become better acquainted.

Upvotes: 5

Views: 2480

Answers (5)

Curtis Autery
Curtis Autery

Reputation: 76

Late to the party, but here's a clean solution that's safe for gnu-apl, not using the power operator, and slightly tweaking Lobachevsky's "neg-two take" method:

fib ← {{⍵, +/ ¯2↑ ⍵} / ⌽ ⍳⍵}

The basic trick is reversing the iota list, since compression reads it in backwards. Sample output:

      fib 10
 1 1 2 3 5 8 13 21 34 55

Upvotes: 1

Tobia
Tobia

Reputation: 18831

I love APL's symbols too, as well as its array programming power. Other array languages may be more powerful, such as J, but they lack the beauty of APL's symbols and explicit syntax.

I just tried the example you link to in GNU APL and it works all right:

      ↑0 1↓↑+.×/5/⊂2 2⍴1 1 1 0
5
      ↑0 1↓↑+.×/6/⊂2 2⍴1 1 1 0
8
      ↑0 1↓↑+.×/7/⊂2 2⍴1 1 1 0
13

If you can't get it to work, make sure to:

  • type (or copy and paste) the exact symbols shown in the example: in particular × is U+00D7 MULTIPLICATION SIGN, not an X; ⍴ is U+2374 APL FUNCTIONAL SYMBOL RHO, not any other Greek Rho, and definitely not a P; ⊂ is U+2282 SUBSET OF; and so on;
  • test some numbers other that 1 or 5, because they are the only numbers that are equal to their Fibonacci number;
  • if you are not putting an actual number in place of N, make sure you define N in a proper way, such as N←7 by itself in a previous line.

If you still can't get it to work, type the formula one step at a time, starting from the right:

      2 2⍴1 1 1 0
1 1
1 0
      ⊂2 2⍴1 1 1 0
 1 1 
 1 0 
      7/⊂2 2⍴1 1 1 0
 1 1   1 1   1 1   1 1   1 1   1 1   1 1 
 1 0   1 0   1 0   1 0   1 0   1 0   1 0 
      +.×/7/⊂2 2⍴1 1 1 0
 21 13 
 13  8 
      ↑+.×/7/⊂2 2⍴1 1 1 0
21 13
13  8
      0 1↓↑+.×/7/⊂2 2⍴1 1 1 0
13
 8
      ↑0 1↓↑+.×/7/⊂2 2⍴1 1 1 0
13

As for the question title, I think this matrix formula nails it (bravo @mappo!)

If I were golfing, I'd probably use a shorter variation, but that's all:

      2⌷∊+.×/7/⊂∘.∨⍨1 0
13

There, from 24 to 17 chars. See if you can figure it out :-)

GNU APL is ok, although it lacks some modern features, but keep a copy of Dyalog APL Programmer's Guide & Language Reference handy, because it's one of the most comprehensive references about the language.

Upvotes: 3

mappo
mappo

Reputation: 476

Alright, I think I've found a way to generate the sequence of length N (rather than the Nth number) in a single (albeit not-so pretty line of APL2):

+/¨(⊂0 0)⍉¨⊖¨(2/¨⍳N)↑¨⊂P←V∘.!V←⍳1+N←20

Like I said: not so pretty. Let me try to break it down into the idioms:

This is the Pascal Triangle with 20 tiers:

P←V∘.!V←⍳1+N←20

Then we take the N first upper-left-corner squares:

(2/¨⍳N)↑¨⊂P

This idiom returns the main diagonal of a matrix:

(⊂0 0)⍉

But we want the anti-diagonal, so before that we'll use ⊖ to flip all squares.

Last step is just to sum all the anti-diagonals with +/.

Upvotes: 2

Thomas Baruchel
Thomas Baruchel

Reputation: 7517

Are you using Dyalog APL? In which case, you should take advantage of the power operator as explained by the previous answer (the first piece of code in that answer coming from the book Mastering Dyalog APL, p. 416).

Another solution with the same operator would be with matrices:

(+.×⍣10)⍨ 2 2⍴1 1 1 0

or as a direct function:

{⊃(+.×⍣⍵)⍨2 2⍴1 1 1 0} 10

If you don't want to use the power operator, you may still use matrices (code below tested under GNU APL 1.5):

{+.×/⍵⍴⊂2 2⍴1 1 1 0} 10

Upvotes: 2

Lobachevsky
Lobachevsky

Reputation: 1252

Another way to do this would be using the (relatively new) power operator. This may or may not yet be supported by GNU APL, it works with Dyalog (I'm using 13.1) and NGN APL.

Try 

 ({⍵,+/¯2↑⍵} ⍣ 20) (1 1)

Like the other examples, the iteration is hidden, here with the power operator.

The expression 

({⍵,+/¯2↑⍵} ⍣ 3) (1 1)

is doing

{⍵,+/¯2↑⍵} {⍵,+/¯2↑⍵} {⍵,+/¯2↑⍵} 1 1

under the covers.

1 1 is the seed value and every successive {⍵,+/¯2↑⍵} simply catenates the sum of the last two elements.

Upvotes: 5

Related Questions