۹ - ۸ستون‌ها و محاسبه‌ی نااکید

همونطور که دیدیم، لیست‌ها یک سریِ بازگشتی از سلول‌‌های cons، ‏‎a : [a]‎‏، هستن که به یه لیست خالی ‏‎[]‎‏ ختم میشن، ولی می‌خوایم یه شناخت بصری هم برای درک بهتر از روشِ پردازش لیست‌ها پیدا کنیم. وقتی از ساختارهای داده در هسکل صحبت می‌کنیم (بخصوص لیست‌ها، سکانس‌ها و درخت‌ها)، میگیم که اونها ستون دارن. این همون ساختارِ اتصالی‌ه که مقادیر رو به هم گره میزنه. در مورد لیست، وقتی می‌خوایم ستون رو با نوشته نشون بدیم، معمولاً با عملگرهای ‏‎(:)‎‏ بصورتِ بازگشتی نشون میدیم. مثلاً با داده ِ ‏‎[1,2,3]‎‏، چنین لیستی می‌گیریم:

1 : 2 : 3 : []
یا
1 : (2 : (3 : []))

اگه سعی کنیم بِکِشیم‌ش، چنین چیزی میشه:

  :
 / \
1   :
   / \
  2   :
     / \
    3  []

مشکلِ ‏‎1 : (2 : (3 : []))‎‏ اینه که طوری لیست رو نشون میده که انگار ۱ "قبل" از سلول ِ cons ِش (سلولی که حاویِ ۱ ِه) وجود داره، ولی در حقیقت این سلول‌‌های cons هستن که مقادیر رو در خودشون دارن. به خاطرِ این مسئله، و طرزِ کارِ محاسبات نااکید، میشه سلول‌‌های cons رو مستقل از محتویات‌شون محاسبه کرد. میشه فقط ستون ِ لیست رو بدون محاسبه‌ی مقادیر حساب کرد. حتی میشه فقط بخشی از ستون ِ یه لیست رو به تنهایی محاسبه کرد.

اگه برمبنای شکلِ بالا بخوایم صحبت کنیم، محاسبه‌ی لیست از بالا به پایینِ ستون پیش میره. ولی ساختِ لیست (هروقت لازم باشه)، از پایین به بالای ستون پیش میره. پس در محاسبه‌ی مثال بالا، از یه عملگر ِ میانوند شروع می‌کنیم، آرگومان‌های ۱ و یه سلول ِ جدیدِ cons رو محاسبه می‌کنیم، و به پایین ادامه میدیم تا به ۳ و لیست خالی برسیم. اما هروقت لازم داریم لیست رو بسازیم، مثلاً برای چاپ در REPL، پیشروی از پایین به بالای ستون ِ لیست انجام میشه، یعنی اول ۳ رو داخل لیست خالی میذاره، بعد ۲ رو پشت اون اضافه می‌کنه و نهایتاً هم ۱ رو پشت اون قرار میده. به خاطرِ نااکید بودنِ محاسبات هسکل، لیست تا وقتی که مصرف نشه ساخته هم نمیشه – البته هیچ چیز تا وقتی لازم نباشه ساخته نمیشه. تا وقتی که لیست مصرف نشه یا محاسبه‌ش از راه دیگه اجبار نشه، یک سری جاگیر به عنوانِ ساختار لیست وجود دارن که هروقت لازم شد، لیست از روی اونها درست بشه. به زودی از نااکید بودن بیشتر صحبت می‌کنیم.

برای نشون دادنِ برخی از تأثیراتِ محاسباتِ نااکید، دوباره از تهی یا ⊥ در فرمِ ‏‎undefined‎‏ استفاده می‌کنیم. با خط تیره هم مقادیری که نادیده می‌گیریم و محاسبه نمی‌کنیم رو نشون میدیم، که در واقع همون مقادیرِ داخلِ سلول‌‌های cons هستن. ستون هم یک سریِ بازگشتی از سازنده‌‌های cons ِه، که این پایین هم نشون دادیم:

  : <------|
 / \       |
_   : <----| اینه (spine یا) "ستون"
   / \     |
  _   : <--|
     / \
    _  []

لغتِ ستون رو در توصیف بقیه‌ی ساختارهای داده غیر از لیست هم می‌بینین (مثل درخت‌‌ها). در مورد لیست، ستون، یک سلسله‌ی خطی از یک سلول ِ cons ِه که یک سلول ِ cons ِدیگه رو در بَر گرفته. اما در ساختارهای داده‌ای مثل درخت‌‌ها (که بعداً توضیح میدیم) می‌بینین که ستون می‌تونه گره‌هایی باشه که دو گره یا بیشتر رو در خودشون دارن.

استفاده از دستورِ ‏‎:sprint‎‏ در GHCi

با یکی از دستورهای GHCi به اسمِ ‏‎sprint‎‏، میشه متغیرها رو چاپ کرد و دید چه چیزهایی حساب شدن و چه چیزهایی نشدن (که مقادیرِ حساب‌نشده با خطِ تیره نشون داده میشن).

هشدار: ما همیشه بعد از دیدن مثال‌های کتاب، شما رو به کاوش و تست برای خودتون تشویق می‌کنیم. اما ‏‎:sprint‎‏ خصلت‌های خاصی داره که ممکن کلافه‌کننده باشن.

در GHC ِ هسکل، بهینه‌سازی‌های فرصت‌طلبانه‌ای تعبیه شدن، و در مواقعی که اثری بر نحوه‌ی محاسبه‌ی کُدتون نداشته باشن، برای تسریع در محاسبات، اَکید بودن رو به کُد اعمال می‌کنن. از طرف دیگه، پلی‌مورفیسم‌ها (یعنی مقادیری مثل ‏‎Num a => a‎‏) در واقع منتظر یه جور آرگومان هستند تا معیّن بشن (این رو در یکی از فصل‌های بعدی با جزئیات بیشتر توضیح میدیم). برای دوری از چنین چیزی، باید تایپ‌های معیّن‌تری مثلِ ‏‎Int‎‏ یا ‏‎Double‎‏ تخصیص بدین، در غیرِ اینصورت، در خروجیِ ‏‎:sprint‎‏ محاسبه‌نشده (‏‎_‎‏) باقی می‌مونن. اگه این خصلت‌های ‏‎:sprint‎‏ رو به خاطر بسپارین، می‌تونه دستور مفیدی باشه. ولی اگه داشت گیج‌تون می‌کرد، کمی صبر کنین تا در فصلِ نااکیدی کامل‌تر توضیح بدیم.

با تابعِ ‏‎enumFromTo‎‏ یه لیست تعریف می‌کنیم (که میشد با گرامر ِ بازه‌ایِ ‏‎['a'..'z']‎‏ هم تعریف کنیم)، بعد وضعیتِ محاسبه‌ش رو با ‏‎:sprint‎‏ بررسی می‌کنیم:

Prelude> let blah = enumFromTo 'a' 'z'
Prelude> :sprint blah
blah = _

منظور از ‏‎blah = _‎‏ اینه که ‏‎blah‎‏ اصلاً محاسبه نشده.

حالا یک المان از ‏‎blah‎‏ رو می‌گیریم و با چاپ در GHCi، محاسبه‌ش رو اجبار می‌کنیم:

Prelude> take 1 blah
"a"
Prelude> :sprint blah
blah = 'a' : _

پس یک سلولِ cons و یک مقدارِ ‏‎'a'‎‏ رو محاسبه کردیم.

این بار دو مقدار می‌گیریم و چاپ می‌کنیم – که محاسبه‌ی سلول cons ِ دوم و مقدارِ دوم رو اجبار می‌کنه:

Prelude> take 2 blah
"ab"
Prelude> :sprint blah
blah = 'a' : 'b' : _

اگه فرض کنیم این دو تا کُد در یک جلسه ِ GHCi نوشته شدن، سلول cons و مقدار اول قبلاً اجبار شده بودن.

میشه این محاسبه‌ی تک‌به‌تکِ مقادیر لیست رو ادامه داد:

Prelude> take 3 blah
"abc"
Prelude> :sprint blah
blah = 'a' : 'b' : 'c' : _

تابعِ ‏‎length‎‏ فقط در محاسبه‌ی ستون‌‌ها اَکید ِه، یعنی فقط محاسبه‌ی ستون ِ یه لیست رو اجبار می‌کنه، و نه مقادیرش رو. با اعمال ِ ‏‎length‎‏ به یه لیست از مقادیرِ ‏‎undefined‎‏ میشه چنین چیزی رو امتحان کرد. ولی اگه ‏‎length‎‏ رو به ‏‎blah‎‏ اعمال کنیم، ‏‎:sprint‎‏ طوری رفتار می‌کنه که انگار محاسبه‌ی مقادیرش رو هم اجبار کردیم:

Prelude> length blah
26
Prelude> :sprint blah
blah = "abcdefghijklmnopqrstuvwxyz"

همین مورد که بعد از گرفتن طول ِ ‏‎blah‎‏، تک‌تکِ حروف رو به عنوانِ مقادیرِ محاسبه‌شده نشون داده (و نه ستون رو به تنهایی) از خصیصه‌های عجیبِ GHCi در نحوه‌ی محاسبه‌ی کُده، که بالاتر اشاره کردیم.

ستون‌ها مستقل از مقادیر محاسبه میشن

مقادیر در هسکل، به طورِ پیش‌فرض تا حالت معمولی با سرِ ضعیف محاسبه میشن. منظور از "حالت معمولی" یعنی بیانیه کاملاً محاسبه بشه. "حالت معمولی با سر ضعیف" یعنی بیانیه فقط تا جایی که برای رسیدن به یه داده‌ساز لازمه ساده بشه.

حالت معمولی با سرِ ضعیف یا WHNF مجموعه‌ی بزرگتریه که هم امکان محاسبه‌ی کامل بیانیه (حالت معمولی) و هم امکان محاسبه‌ی بیانیه، فقط تا رسیدن به یه داده‌ساز (یا لاندایی که منتظرِ یه آرگومان هست) رو شامل میشه. یه بیانیه در حالت معمولی با سر ضعیف، ممکنه با داشتن یه آرگومانِ دیگه ساده‌تر بشه. اگه دیگه نمی‌تونه ورودی بگیره، اون موقع علاوه بر WHNF، در حالت معمولی (NF) هم هست. جلوتر در کتاب، در فصلی که از نااَکید بودن صحبت می‌کنیم و طرز کارِ فراخوان بر مبنای نیاز در هسکل رو نشون میدیم، این مباحث رو خیلی کامل‌تر توضیح میدیم. فعلاً با چندتا مثال کار می‌کنیم تا یه درکِ اجمالی پیدا کنیم.

در زیر چند بیانیه، به همراه اینکه آیا در ‏‎NF‎‏، ‏‎WHNF‎‏، هردو یا هیچ کدوم هستن می‌نویسیم:

(1, 2) -- NF و WHNF

این مثال اول در حالت معمولی ِه و کاملاً محاسبه شده. بنا بر تعریف، هر چیزی که در حالت معمولی باشه، در حالت معمولی با سر ضعیف هم هست، چون بیانیه با سرِ ضعیف، حداقل تا اولین داده‌ساز محاسبه میشه. در نتیجه حالت معمولی فراتر میره، چون همه‌ی زیر-بیانیه‌هاش هم باید کاملاً محاسبه شده باشن. مقداری که در مثال بالا نوشتیم شامل اجزای: داده‌ساز ِ توپل، و مقادیرِ ۱ و ۲ ِه.

(1, 1 + 1)

این مثال در WHNF هست ولی در NF نیست. تابعِ ‏‎(+)‎‏ به همراه آرگومان‌هاش می‌تونه ساده‌تر بشه، اما هنوز نشده.

\x -> x * 10 -- NF و WHNF

با اینکه ‏‎(*)‎‏ در این تابع به هر دو آرگومان‌هاش اعمال شده، ولی تا وقتی ‏‎x -> ...‎‏ ِ بیرونی مشخص نشه ساده‌تر هم نمیشه، پس این تابعِ بی‌نام ساده‌تر نمیشه و در حالت معمولی ِه.

"Papu" ++ "chon"

این الحاق ِ نوشته نه در WHNF ِه و نه در NF، چون بیرونی‌ترین جزء این بیانیه، یه تابع‌ه، ‏‎(++)‎‏، که همه‌ی آرگومان‌هاش اعمال شدن ولی هنوز محاسبه نشده. در مقابل، این یکی بیانیه در WHNF هست ولی در NF نیست:

(1, "Papu" ++ "chon")

وقتی یه لیست، و همه‌ی مقادیرش رو تعریف می‌کنیم، در NF هست و همه‌ی مقادیرش مشخص‌اند. اون موقع چیزی برای محاسبه نمونده، مثل زیر:

Prelude> let num :: [Int]; num = [1,2,3]
Prelude> :sprint num
num = [1,2,3]

اما اگه لیست رو با بازه‌ها یا توابع درست کنیم، لیست WHNF میشه ولی NF نمیشه. کامپایلر فقط سَر یا اولین گره ِ گراف رو محاسبه می‌کنه، یعنی فقط سازنده ِ cons رو، نه مقدارِش یا لیست‌های دیگه که شامل‌ش هستن. می‌دونیم در سلول cons ای که محاسبه نکردیم، یک مقدار با تایپِ ‏‎a‎‏ و یه "مابقیِ لیست" هست که ممکنه یا یه لیست خالی ‏‎[]‎‏ باشه (و در نتیجه لیست رو پایان بده) یا یه سلول cons دیگه – نمی‌دونیم چیه چون هنوز مقدارِ ‏‎[a]‎‏ ِ بعدی رو محاسبه نکردیم. مثالی از این رو بالاتر در بخشی که ‏‎:sprint‎‏ رو معرفی کردیم دیدیم، و میشه دید که محاسبه‌ی مقادیرِ اول، محاسبه‌ی مابقی لیست رو اجبار نمی‌کنه:

Prelude> let myNum :: [Int]; myNum = [1..10]
Prelude> :sprint myNum
myNum = _
Prelude> take 2 myNum
[1,2]
Prelude> :sprint myNum
myNum = 1 : 2 : _

این یه مثال از محاسبه‌ی WHNF ِه. به خاطر اینکه لیست باید از بازه درست بشه، در حالت معمولی با سر ضعیف ِه و فقط تا جایی که مجبور هست محاسبه میشه. با ‏‎take 2‎‏، فقط محاسبه‌ی دو سلول cons ِ اول و مقادیرشون لازمه، به همین خاطر با ‏‎:sprint‎‏ فقط ‏‎1 : 2 : _‎‏ رو دیدیم. محاسبه تا حالت معمولی یعنی کل لیست رو پیش بریم، و نه تنها کلِ ستون، بلکه مقادیری که تک‌تکِ سلول‌‌های cons دارن رو هم محاسبه کنیم.

در این نمایشِ درختی از لیست‌ها، محاسبه یا مصرف ِ لیست، به سمتِ پایین ِ ستون پیش میره. مثال زیر از یه لیست‌ه که ستون ِش محاسبه نشده، و منتظر یه چیزیه که مجبورش کنه:

  :
 / \
_   _

به طور پیش‌فرض همین‌جا متوقف میشه و حتی اولین سلول cons ِش هم محاسبه نمیشه، مگر اینکه مجبور بشه (که قبلاً هم دیدیم).

توابعی که مؤکدِ ستون هستن، ممکنه محاسبه‌ی کلِ ستون ِ لیست رو، بدون محاسبه‌ی تک‌تکِ مقادیر اجبار کنن. تطبیق الگو به طور پیش‌فرض اَکید ِه، پس اگه تابعی روی سلول‌‌های cons تطبیق الگو انجام بده و تا آخرِ لیست پیش بره، اون تابع می‌تونه مؤکدِ ستون باشه. بسته به محتوای تابع، ممکنه فقط ستون ِ لیست رو محاسبه کنه، یا علاوه بر ستون ِ لیست، مقداری که داخل هر سلول cons هست هم حساب کنه.

تابعِ ‏‎length‎‏ یک نمونه تابعی‌ه که فقط مؤکدِ ستون ِه اما مقادیر رو اجبار به محاسبه نمی‌کنه. استفاده از ‏‎length‎‏ روی لیستی مثل ‏‎[1,2,3]‎‏ محاسبه‌ی کلِ ستون رو، بدون محاسبه‌ی مقادیر اجبار می‌کنه:

  :
 / \
_   : 
   / \
  _   :
     / \
    _  []

اگه یکی از مقادیر رو با ‏‎undefined‎‏ تهی کنیم، میشه چنین چیزی رو به وضوح دید:

Prelude> let x = [1, undefined, 3]
Prelude> length x
3

مقادیرِ اول و سوم عدد بودن، اما مقدار دوم تهی بود، با این حال ‏‎length‎‏ خطا نداد. چرا؟ چون ‏‎length‎‏ طولِ لیست رو اندازه می‌گیره، که اون هم فقط با بررسیِ ستون و شمارشِ سلول‌‌های cons انجام میده. می‌تونیم تابعِ ‏‎length‎‏ ِ خودمون رو بنویسیم:

-- length دقیقاً معادل تابع
-- *نیست* Prelude در
length :: [a] -> Integer
length [] = 0
length (_:xs) = 1 + length xs

همونطور که گفتیم، از خط تیره برای نادیده گرفتن ِ مقادیر آرگومان‌ها (یا بخشی از آرگومان‌ها) استفاده می‌کنیم. در این مورد هم روی داده‌ساز ِ ‏‎(:)‎‏ تطبیق الگو انجام دادیم، ولی مقدارِ اولین آرگومان‌ش رو نادیده گرفتیم. دقت کنین که این انقیاد ِ مراجع در سمت چپ به ‏‎_‎‏، در حدِ رسم و رسوم نیست. نمیشه آرگومان‌ها رو به اسمِ "‏‎_‎‏" انقیاد داد؛ این نوشتار جزئی از زبان‌ه. یکی از دلایل‌ش اینه که کامپایلر مطمئن باشه با مقدارِ نادیده گرفته شده هیچ محاسباتی انجام نمیشه. در حال حاضر اگه از ‏‎_‎‏ در سمت راستِ یک تعریف استفاده کنین، کامپایلر فکر می‌کنه به یه سوراخ اشاره می‌کنین.

برای شمارشِ مقادیر داخل لیست، فقط داده‌ساز ِ ‏‎(:)‎‏ و ‏‎[]‎‏ در آخر رو اجبار می‌کنیم:

      :       <-|
     / \        |
|-> _   :     <-|
|      / \      | اینها محاسبه (اجبار) شدن
|->   _   :   <-|
|        / \    |
|->     _  [] <-|
|
| اما اینها نشدن

اگه بخشی از خودِ ستون تهی باشه، ‏‎length‎‏ هم خطا میده:

Prelude> let x = [1] ++ undefined ++ [3]
Prelude> x
[1 *** Exception: Prelude.undefined
Prelude> length x
*** Exception: Prelude.undefined

چاپ ِ لیست شکست خورد، البته تا جایی که تونست پیش رفت (مقدار و ‏‎[‎‏ ِ اول)، تلاش برای پیدا کردنِ طول ِ لیست هم شکست خورد چون نمی‌تونه ستون ِ تعریف‌نشده رو بشماره.

نوشتنِ توابعی که هم ستون و هم مقادیر رو اجبار کنند هم ممکنه. تابعِ ‏‎sum‎‏ یه نمونه‌ست، چون برای پیدا کردنِ مجموعِ همه‌ی مقادیرِ لیست باید مقدارِ همه‌ی المان‌ها رو بدونه.

اینجا خودمون تابعِ ‏‎sum‎‏ رو تعریف می‌کنیم تا بهتر نشون بدیم:

mySum :: Num a => [a] -> a
mySum [] = 0
mySum (x : xs) = x + mySum xs

اول اینکه عملگر ِ ‏‎+‎‏ هر دو آرگومان رو اجبار می‌کنه، پس مقادیرِ ‏‎x‎‏ و ‏‎xs‎‏ باید اول حساب بشن. درنتیجه ‏‎mySum‎‏ همینطور بازگشتی ادامه میده تا به لیست خالی برسه و متوقف شه. بعد شروع به بالا رفتن از ستون ِ لیست و جمع کردنِ اعضای اون می‌کنه. چیزی شبیهِ این (صفر، لیست خالی رو نشون میده):

Prelude> mySum [1..5]
1 + (2 + (3 + (4 + (5 + 0)))) 
1 + (2 + (3 + (4 + 5)))
1 + (2 + (3 + 9))
1 + (2 + 12)
1 + 14
15

در نقاطِ مختلفِ کتاب باز هم به این موضوع برمی‌گردیم، چون درک خوب از سیاست‌های هسکل در محاسبات، زمان و تمرین لازم داره. اگه الان حس می‌کنین کامل درک‌ش نکردین، موردی نداره. مبحثِ پیچیده‌ایه و بهتره آدم مرحله به مرحله یاد بگیره.

تمرین‌ها: دیوانگی پوچ

منفجر میشه؟

آیا بیانیه‌های زیر یک مقدار برمی‌گردونن یا ⊥؟

[x^y | x <- [1..5], y <- [2, undefined]]

take 1 $
[x^y | x <- [1..5], y <- [2, undefined]]

sum [1, undefined, 1]

length [1, 2, undefined]

length $ [1, 2, 3] ++ undefined

take 1 $ filter even [1, 2, 3, undefined]

take 1 $ filter even [1, 3, undefined]

take 1 $ filter odd [1, 3, undefined]

take 2 $ filter odd [1, 3, undefined]

take 3 $ filter odd [1, 3, undefined]

آنتراکت: در حالت معمولی هست؟

برای هر کدوم از بیانیه‌های زیر تعیین کنین که:

یادتون باشه که اگه بیرونی‌ترین بخشِ بیانیه یه داده‌ساز نباشه، نمی‌تونه در حالت معمولی یا حالت معمولی با سر ضعیف باشه. اگه هر بخشی از بیانیه محاسبه نشده باشه، نمی‌تونه در حالت معمولی باشه.

[1, 2, 3, 4, 5]

1 : 2 : 3 : 4 : _

enumFromTo 1 10

length [1, 2, 3, 4, 5]

sum (enumFromTo 1 10)

['a'..'m'] ++ ['n'..'z']

(_, 'b')