Map, Fold, Lambda ve Fonksiyonel Programlama Üzerine

Giriş

Son 5 aydır eski adı ile PLT-Scheme, yeni adı ile Racket kullanarak problemler çözüyor ve fonksiyonel programlamanın güzelliklerini görüyoruz . Her programcının hayatının belli bir bölümünü fonksiyonel programlama ile geçirmesi gerçek anlamda çok yararlı oluyor ve düşünce yapısını değiştiriyor. Bu konu farklı bir blog girdisinin konusu olacağı için konuya fazla eğilmeden başlıkta da belirttiğim şeyler hakkında bir şeyler karalamayı planlıyorum.

Bu blog girdisinde map, fold ve lambda’nın ne olduğuna ve nasıl çalıştığına değinip, bunları kullanarak çözülebilecek güzel bir problem yazacağım. Bahsedilen fonksiyonlar birçok programlama dillerinde mevcut ve hepsinin altında yatan mantık aynı. Yazının daha rahat anlaşılır olabilmesi adına Racket’in sözdizimine değinmek yararlı olacak. Genel olarak Racket’a giriş, high-order fonksiyonların tanımı üzerine yoğunlaşan bir yazı olacak.

(Kodların renklendirilmemesinden ötürükusura bakmayınız. Anladığım kadarıyla WordPress Racket için kod renklendirmesi desteklemiyor)

Racket, infix prefix notation diye tabir edilen, prosedürlerin önce geldiği, sonrasında parametrelerin yer aldığı bol parantezli bir dil. Tipik bir toplama işlemi

(+ 2 3)
(+ 2 3 4 5 6)

şeklinde yapılıyor. Burada +, iki veya daha çok sayı cinsinden parametre alabilen ve sayıların toplamını döndüren bir fonksiyon. Tıpkı matametikte olduğu gibi, iç içe geçmiş fonksiyonlar da yazabiliyoruz. 3 4 ve 5 sayılarını toplayıp, sonrasında elde edilen rakamı 2 ile çarpmak istersek;

(* 2 (+ 3 4 5))

yazmamız yeterli olacaktır. Bir fonksiyon tanımlamayı define prosedürü ile yapıyoruz. iki parametre alan ve bunları birbiri ile çarpan basit bir fonksiyonu aşağıdaki gibi tanımlayabiliriz.


(define (carp bir iki)

(* bir iki))

Daha fazlası için How to Design Programs kitabını okuyabilirsiniz. Şimdilik bu kadar işimizi görecek.

Lambda

Yukarıda, bir fonksiyon tanımladık ve buna bir isim verdik. Ancak her fonksiyona bir isim vermek zorunda mıyız? Hayır. Lambda bu noktada işimize yarıyor. Lambda’yı bize bir fonksiyon döndüren anonim bir fonksiyon olarak adlandırabiliriz. Örneğin bir parametre alan ve bunun karesini döndüren bir fonksiyon elde etmek istiyorsak


(lambda (x) (sqr x))

yazmamız yeterli olacaktır. Bu yukarıda yaptığımız toplama işlemindeki gibi kullanabiliriz. Hatırlayın, prosedürler önce ve parametreler sonra geliyor. Eğer lambda bize bir fonksiyon döndürüyorsa, bu fonksiyonu direkt olarak çağırabilir ve işimizi halledebiliriz. Öyleyse;

((lambda (x) (sqr x)) 2)

bize 4 sonucunu verecektir. Lambda, high-order fonksiyonları kullanırken çok işimize yarayacak. Devam etmeden önce bildiğiniz bir programlama dilini kullanarak bunun üzerinde biraz pratik yapmanız yararlı olacaktır.

High-Order Functions

High-order fonksiyonlar, genel olarak, en azından parametre olarak bir fonksiyon alan veya çıktı olarak bir fonksiyon döndüren fonksiyonlardır. Fonksiyonumuz bir veri almak yerine, bir fonksiyon alabilir ve bununla harikalar yaratabiliriz. İşte Racket’taki map, foldr, foldl, filter gibi fonksiyonlar bu kategoriye girer. Diğer programlama dillerinde de map, fold ve filter mevcut.

High-order fonksiyonlar, listeleri işlemede bize büyük kolaylıklar sağlıyor.  Map, listedeki her eleman üzerinde işlem yaparak, işlem sonrasında çıkan sonucu bir liste halinde döndürür. Filter ise, her eleman üzerinde işlem yaparak, bizim belirttiğimiz kurallara uyan liste elemanlarını seçip, bir liste döndürüyor. Adından da anlaşılacağı gibi, belli bir koşula bağlı olarak liste elemanlarını filtreliyor.

Biraz daha açacak olursak. Map, kendisine ilk parametre olarak, tek bir parametre kabul eden ve sonuçta bir şey döndüren bir fonksiyon alıyor, ikinci parametre olarak da üzerinde bu fonksiyonun uygulanacağı liste alıyor. Sonrasında, listenin her elemanını teker teker alıp, o fonksiyona parametre olarak veriyor, fonksiyondan dönen sonucu yeni bir liste halinde bize sunuyor. Listedeki her sayıyı bir arttıran bir map ifadesi şu şekilde yazabiliriz;


(map (lambda (parametre) (+ 1 parametre)) (list 1 2 3 4 5))

Burada dikkatinizi lambda’ya çekmek istiyorum. Map ilk parametre olarak bir fonksiyon alıyor demiştik. Bu fonksiyonu dışarıda bir yerde tanımlamak yerine, lambda ile o fonksiyonu oluşturduk ve map’e parametre olarak verdik. İstersek listedeki her elemanın karesini de şu şekilde alabilirdik;


(map sqr (list 1 2 3 4 5))

Sqr fonksiyonu, bir parametre alan ve sonucunda o sayının karesini döndüren bir fonksiyondur. Burada lambda’nın ve map’in ne iş yaptığını daha iyi görebileceğinizi umuyorum. Genellikle high-order fonksiyonları kullanırken fonksiyonlar dışarıda tanımlanmaz ve lambda ile hızlı bir biçimde işlem yapılır.

Filter da map ile aynı mantıkta çalışıyor ancak kendisine parametre olarak aldığı fonksiyonun boolean bir veri, yani doğru veya yanlış döndürmesini bekler. Bunu her liste elemanının kontrolünü sağlıyor gibi düşünebiliriz. Eğer o liste elemanı fonksiyona giriyor, ve sonucunda True dönüyor ise, o eleman çıktıdaki listede yer alacaktır. (1 3 4 5 7 88) listesindeki 4ten büyük elemanları almak için aşağıdaki kodu kullanabiliriz.


(filter (lambda (x) (> x 4)) (list 1 3 4 5 7 88))



Tekrar hatırlatmak isterim. Listedeki her eleman sıra ile fonksiyona parametre olarak gönderiliyor, eğer fonksiyondan dönen sonuç True ise, sonrasında döndürülecek olan listeye ekleniyor, değilse zaten listede yer almıyor.

Fold, map ve filter’dan biraz daha karışık. Map gibi birinci parametre olarak fonksiyon alıyor ancak bu fonksiyon iki parametreli. Sonraki parametre olarak iterasyona başlamak için bir veri, ve en son olarak da üzerinde işlem yapacağı listeyi alıyor. Tipik bir foldr prosedürü şu şekilde;


(foldr (lambda (x y) (* x y)) 1 (list 2 3 4 5))

Foldr, listenin sağından başlayarak işlem yapıyor ve akümülatif çalışıyor. Buradaki mantık şu. Listeyi işlerken, fold’a verdiğimiz fonksiyonun ilk parametresi, yani buradaki “x”, her zaman listenin elemanları, “y” ise bir önceki fonksiyon çağrısından dönen sonuç. Listeyi işlemeye başlarken, fonksiyonun ilk çağrılışında, daha önce bir fonksiyon çağrısı olmadığı ve sonuç dönmediği için, “y” parametresi, fold’a verdiğimiz ikinci parametre oluyor. Yani fold başlarken, “x” 5, “y” 1 değerini alıyor ve fonksiyona giriyor. Bu fonksiyon da her iki değeri çağırıp “5” sonucunu döndürüyor. Şimdi sıra listenin ikinci elemanında. “x” parametresi 4 değerini alıyor, bir önceki çağrıdan gelen 5 sonucu da “y” değeri oluyor. İkisi çarpılıyor ve 20 sonucu çıkıyor. Sıra üçüncü elemanda. “x” 3 değerini alıyor, “y” 20 değerini alıyor ve çarpılarak sonuç 60 çıkıyor. Ve sıra geldi son elemana. Son “x” 2 değerini alırken “y” 60 değerini alıyor ve foldr fonksiyonumuz 120 değerini döndürüyor.

Basit olarak lambda, map, filter ve fold bu işlere yarıyor. Geliştirip daha farklı şeyler yapmak pratikle kazanılabilecek bir şey. Kullanım alanında sınır mevcut değil. Örnek olarak, map içerisinde fold kullanıp, çıkan sonucu filtreleyebilir ve oradan dönen liste üzerinde de işlem yapabiliriz. Bu noktada “sky is the limit” :)

Soru

Elimizde içerisinde sayı listesi barındıran bir liste olsun. Örneğin ((1 2) (3) (4 5)). Tasarlayacağımız fonksiyon da bu listeyi alıp, kartezyen çarpımlarını yine sayı listesi barındıran bir liste halinde döndürsün. Yani fonksiyonumuza ((1 2) (3) (4 5)) verdiğimizde bize ((1 3 4) (1 3 5) (2 3 4) (2 3 5)) döndürmeli.

Lakin burada bazı kısıtlamalar var. Tasarlayacağımız fonksiyon sadece map, filter, fold kullanabilir ve fonksiyonun gövdesinde “if, else” gibi ifadeler kullanmamamız gerekiyor. Sadece, high-order fonksiyonlara verdiğimiz fonksiyonlar içerisinde (lambda) “if, else” kullanabiliriz. Mümkünse google’da benzer sorular için aramayın, üzerinde düşünmek gerçekten güzel bir beyin jimnastiği oluyor.

Bunu istediğiniz programlama dilinde çözebilirsiniz. Ben Racket’da yorumları silersek normalde 12 satır, biraz sıkıştırırsak 8 satırda çözdüm ve high-order fonksiyonlar konusunda çok pratiğim olmadığı için yaklaşık olarak 2 saat vaktimi aldı. Sonuçta gayet iyi bir pratik oldu tabi. Çözdüğünüz zaman yorum olarak girmenizi gerçekten isterim. Yaklaşım ve düşünce farklarını görmek ve bunun üzerinde tartışmak yararlı olacaktır.

Her listeden bir eleman, ve küçük parçalara ayırın da ipucunuz olsun :)

Reklamlar

One thought on “Map, Fold, Lambda ve Fonksiyonel Programlama Üzerine

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Connecting to %s