۱۵ - ۱۳نیم‌گروه

اونطوری که ریاضیدان‌ها با جبر بازی می‌کنن، آدم رو یاد اون همکلاسی دوران مدرسه میندازه که پای حشره‌ها رو می‌کَند. بعضی وقتا هم پاهاشون رو می‌چسبونن سر جاش، اما در این مورد که از ‏‎Monoid‎‏ به سمتِ ‏‎Semigroup‎‏ پیش میریم، داریم یه پا رو می‌کَنیم. برای رسیدن به نیم‌گروه از مانوید، فقط کافیه مقدارِ همانی رو حذف کنیم. عملیات ِ اصلی هنوز دوتایی و شرکت‌پذیر باقی می‌مونه.

در نتیجه تعریفِ ‏‎Semigroup‎‏ از این قراره:

class Semigroup a where
  (<>) :: a -> a -> a

فقط هم یک قانون داریم:

(a <> b) <> c == a <> (b <> c)

عملیاتی که ‏‎Semigroup‎‏ ارائه میده هنوز یه عملیات ِ دوتایی و شرکت‌پذیر ِه، که دوتا چیز رو به هم متصل می‌کنه (مثل الحاق یا جمع)، ولی یه مقدارِ همانی نداره. از این لحاظ، جبر ِ ضعیف‌تری به حساب میاد.

هنوز جزئی از ‏‎base‎‏ نیست

تا ۸ GHC، تایپکلاس ‏‎Semigroup‎‏ توی ‏‎base‎‏ هست، اما جزئی از ‏‎Prelude‎‏ نیست. اگه عملیات‌هاش رو لازم داشته باشین باید ‏‎Data.Semigroup‎‏ رو وارد کنین. حواستون باشه که برای خودش یه نسخه‌ی جامع‌تر از ‏‎(<>)‎‏ رو داره که فقط یه محدودیت ِ ‏‎Semigroup‎‏ لازم داره تا محدودیت ِ ‏‎Monoid‎‏.

نوع‌داده ِ ‏‎NonEmpty‎‏ که الان می‌خوایم بگیم رو می‌تونین با وارد کردنِ ‏‎Data.List.NonEmpty‎‏ بیارین تو REPL.

‏‎NonEmpty‎‏، یه نوع‌داده ِ به‌دردبخور

یه نوع‌داده ِ مفید که نمی‌تونه نمونه ِ ‏‎Monoid‎‏ داشته باشه، اما ‏‎Semigroup‎‏ می‌تونه داشته باشه، تایپِ لیستِ ‏‎NonEmpty‎‏ ِه. یه نوع‌داده ِ لیستی‌ه که هیچ‌وقت نمی‌تونه خالی باشه:

data NonEmpty a = a :| [a]
  deriving (Eq, Ord, Show)

-- نمونه‌هاش رو ننوشتیم

این ‏‎:|‎‏ یه داده‌ساز ِ میانوند ِه که دو آرگومان (تایپی) می‌گیره. حاصلضرب ِ ‏‎a‎‏ و ‏‎[a]‎‏ هست. تضمین می‌کنه که همیشه حداقل یک مقدار با تایپ ‏‎a‎‏ داریم، تضمینی که با ‏‎[a]‎‏ نداره، چون ممکنه خالی باشه.

با اینکه برخلافِ اکثرِ داده‌سازهای دیگه‌ای که دیدین، ‏‎:|‎‏ الفباعددی نیست، اسمِ یه داده‌ساز ِ میانوند ِه. داده‌سازهایی که اسم‌شون فقط با علامتهای غیرالفباعددی که با دونقطه شروع میشن تعریف شده، به صورتِ پیش‌فرض میانوندی اند؛ اونهایی هم که الفباعددی اند بطور پیش‌فرض پیشوندی اند:

-- یا پیشوندی prefix
data P =
  Prefix Int String

-- یا میانوندی infix
data Q =
  Int :!!: String

از اونجا که داده‌ساز ِ دوم الفباعددی نیست، نمیشه پیشوندی ازش استفاده کرد:

data R =
  :!!: Int String

خطای گرامری میده:

parse error on input ‘:!!:’
Failed, modules loaded: none.

برعکس‌ش هم هست، از یه داده‌ساز ِ پیشوندی نمیشه میانوندی استفاده کرد:

data S =
  Int Prefix String

یه خطای دیگه میده:

Not in scope: type constructor or class ‘Prefix’
A data constructor of that name is in scope;
did you mean DataKinds?
Failed, modules loaded: none.

برگردیم سرِ اصل مطلب، ‏‎NonEmpty‎‏. از اونجا که ‏‎NonEmpty‎‏ ضرب ِ دو آرگومان‌ه، اینطور هم میشد بنویسیم‌ش:

newtype NonEmpty a =
  NonEmpty (a, [a])
  deriving (Eq, Ord, Show)

برای ‏‎NonEmpty‎‏ نمیشه یه ‏‎Monoid‎‏ نوشت، چون اصلاً طوری طراحی نشده که مقدار همانی داشته باشه. هیچ لیست خالی‌ای وجود نداره که عملیات روی یه لیستِ ‏‎NonEmpty‎‏ رو تبدیل به تابع همانی کنه، ولی عملیات ِ دوتایی ِ شرکت‌پذیر داره: دوتا لیستِ ‏‎NonEmpty‎‏ رو میشه به هم الحاق داد. چنین تایپی که یه عملیات ِ باینری ِ شرکت‌پذیر ِ کانونیک داره ولی مقدارِ همانی نداره با ‏‎Semigroup‎‏ خیلی خوب جور درمیاد. یه مثال اجمالی برای استفاده از ‏‎NonEmpty‎‏ از کتابخونه ِ ‏‎semigroups‎‏ با ‏‎mappend‎‏ ِ نیم‌گروه (تا GHC ۸٫۰٫۱، ‏‎Semigroup‎‏ و ‏‎NonEmpty‎‏ هردو در ‏‎base‎‏ هستن، اما در ‏‎Prelude‎‏ نیستن):

-- رو نصب کنین semigroups ممکنه لازم باشه
Prelude> import Data.List.NonEmpty as N
Prelude N> import Data.Semigroup as S
Prelude N S> 1 :| [2, 3]
1 :| [2,3] 
Prelude N S> :t 1 :| [2, 3]
1 :| [2,3] :: Num a => NonEmpty a
Prelude N S> :t (<>)
(<>) :: Semigroup a => a -> a -> a

Prelude N S> let xs = 1 :| [2, 3] 
Prelude N S> let ys = 4 :| [5, 6] 
Prelude N S> xs <> ys
1 :| [2,3,4,5,6]
Prelude N S> N.head xs
1
Prelude N S> N.length (xs <> ys)
6

غیر از اینها، استفاده از ‏‎NonEmpty‎‏ مشابهِ لیست‌ه، فقط صراحتاً اعلام کردین که برای کاری که دارین انجام میدین، نداشتنِ هیچ مقداری قابل قبول نیست. به خاطر تعریفِ نوع‌داده که نمیذاره بدون مقدار یه ‏‎NonEmpty‎‏ بسازین، چنین محدودیتی تحمیل میشه.